まず、対称性より \(X,Y\) をそれぞれ \(|X|,|Y|\) に置き換えても答えは変わりません。以降は \(X,Y\geq 0\) の場合を考えます。

求める答えを \(f_{A,B}(X,Y)\) とします。

\(X+Y\) が奇数の場合、奇数回目に \((X\pm 1,Y)\) または \((X,Y\pm 1)\) から \((X,Y)\) に移動します。 コストの総和が最小となる移動方法を一つ取ると、\(x=0,X\) と \(y=0,Y\) でそれぞれ適切に折り返すことでコストの総和を変えずに最後の移動を \((X-1,Y)\) または \((X,Y-1)\) から \((X,Y)\) への移動に限定できます。 したがって、\(f_{A,B}(X,Y)=\min(f_{A,B}(X-1,Y)+A,f_{A,B}(X,Y-1)+B)\) が成り立ちます。この式を用いることで \(X+Y\) が偶数の場合に帰着できます。以降は \(X+Y\) が偶数の場合を考えます。

\(X+Y\) が偶数の場合、移動回数も偶数になります。したがって、移動回数を \(2K(\geq X+Y)\) 回とします。このとき、奇数回目の操作と偶数回目の操作の回数は同じなので、\(A,B\) に対称性が生まれます。また、x 座標と y 座標を入れ替える操作を行なっても答えが変わらないことを考えると、\(A > B,X>Y\) である場合にそれぞれ \(A,B\)、\(X,Y\) をそれぞれ swap することで \(A\le B,X\le Y\) の場合に帰着できます。以降は \(A\le B,X\le Y\) も仮定します。

\(Y\) と \(K\) の大小関係で場合分けをします。

[1] \(K\le Y\) のとき

\(2K\geq X+Y\) より、\(K\) の範囲は \(\displaystyle \frac{X+Y}2\le K\le Y\) となります。

\(A\le B\) より、\(2K\) 回の移動の中でコスト \(A\) の移動をできる限り多く行なった方が良いです。しかし、y 座標を増やす移動はコスト \(A\) では \(K\) 回しかできないため最低でも \(K-X\) 回以上はコスト \(B\) の移動を行う必要があります。逆に、 \(K-X\) 回コスト \(B\) の移動を行うことでコマを座標 \((X,Y)\) に移動させることができるので、コストの総和の最小値は \(g(K)=2KA+(Y-K)(B-A)\) となります。

この関数は一次関数であるため、定義域の端で必ず最小値を取ります。したがって、この場合の最小値は \(\displaystyle \min\left(g\left(\frac{X+Y}2\right),g(Y) \right)\) です。

[2] \(Y\le K\) のとき

\(2K\) 回全てコスト \(A\) の移動を行うことでコマを座標 \((X,Y)\) に移動させることができます。したがってコストの総和の最小値は \(2KA\) と書けます。明らかに \(K=Y\) の場合が最適であり、これは既に [1] で議論済みです。

[1], [2] より、求める答えは \(g(K)=2KA+(Y-K)(B-A)\) に対する \(\displaystyle \min\left(g\left(\frac{X+Y}2\right),g(Y) \right)\) です。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(1)\) です。

実装例(Python3)

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))