By symmetry, replacing \(X\) and \(Y\) with \(|X|\) and \(|Y|\), respectively, does not change the answer, so we will assume \(X,Y\geq 0\).

Let \(f_{A,B}(X,Y)\) be the sought answer.

If \(X+Y\) is odd, the piece moves from \((X\pm 1,Y)\) or \((X,Y\pm 1)\) to \((X,Y)\) in an odd-indexed move. If we take a path that minimizes the total cost, flipping it with respect to \(x=0,X\) and \(y=0,Y\) yields a path with the same cost, but the last move is always from \((X-1,Y)\) or \((X,Y-1)\) to \((X,Y)\). Thus, \(f_{A,B}(X,Y)=\min(f_{A,B}(X-1,Y)+A,f_{A,B}(X,Y-1)+B)\). By this equation, the problem is reduced to a case where \(X+Y\) is even. We will now assume that \(X+Y\) is even.

If \(X+Y\) is even, the number of moves is also even. Let \(2K(\geq X+Y)\) be the number of moves. Then odd-indexed and even-indexed moves are performed the same number of times, yielding a symmetry between \(A\) and \(B\). Also, swapping the \(x\) and \(y\) coordinates does not change the answer. Therefore, if \(A > B\) or \(X>Y\), we may swap \(A,B\) or \(X,Y\) to boil down to a case where \(A\le B\) and \(X\le Y\), respectively. Thus we also assume \(A\le B\) and \(X\le Y\).

We discuss by cases depending on which of \(Y\) and \(K\) is larger.

Take a path that minimizes the total cost. Then flipping it with respect to \(x=0,\max(X,1)\) and \(y=0,\max(Y,1)\) yields a path with the same cost, but always moves within \(0\le x\le \max(X,1),0\le y\le \max(Y,1)\). Thus, we may constrain the moving range to \(0\le x\le \max(X,1),0\le y\le \max(Y,1)\).

[1] If \(K\le Y\)

By \(2K\geq X+Y\), \(K\) ranges in \(\displaystyle \frac{X+Y}2\le K\le Y\).

By \(A\le B\), it is optimal to have as many cost-\(A\) moves as possible within the \(2K\) moves. However, moves that increase \(y\) coordinates no more than \(K\) times for cost \(A\), so at least \((K-X)\) moves must be performed for cost \(B\). Conversely, performing cost-\(B\) moves \((K-X)\) times always leads the piece to coordinates \((X,Y)\), so the minimum total cost is \(g(K)=2KA+(Y-K)(B-A)\).

Since this function is affine, it takes the minimum value at either end. Thus, the minimum value for this case is \(\displaystyle \min\left(g\left(\frac{X+Y}2\right),g(Y) \right)\).

[2] If \(Y\le K\)

All \(2K\) moves can be spent to cost-\(A\) moves to lead the piece to coordinate \((X,Y)\). Thus, the minimum total cost required can be written as \(2KA\). Obviously, it is optimal when \(K=Y\), which is already covered by [1].

By [1] and [2], the sought answer equals \(\displaystyle \min\left(g\left(\frac{X+Y}2\right),g(Y) \right)\) where \(g(K)=2KA+(Y-K)(B-A)\).

The problem can be solved by properly implementing the algorithm above. The complexity is \(O(1)\) per test case.

Sample code (Python 3)

input = __import__("sys").stdin.readline


def solve(a, b, x, y):
    assert (x + y) % 2 == 0
    if a > b:
        a, b = b, a
    if x > y:
        x, y = y, x
    return min(2 * a * y, a * (x + y) + (b - a) * (y - x) // 2)


for _ in range(int(input())):
    a, b, x, y = map(int, input().split())
    x, y = abs(x), abs(y)
    if (x + y) % 2 == 1:
        print(min(solve(a, b, x - 1, y) + a, solve(a, b, x, y - 1) + b))
    else:
        print(solve(a, b, x, y))