题目描述

给定整数 $A, B, X, Y$。

在一个二维平面上放置了一个棋子。初始时，棋子位于坐标 $(0, 0)$。

你可以执行零次或多次以下操作：

• 将棋子朝上下左右四个方向中的一个移动一格。

第 $k$ 次操作 ($k \ge 1$) 的代价取决于 $k$ 的奇偶性，具体规则如下：

• 如果 $k$ 为奇数：从 $(x, y)$ 移动到 $(x-1, y)$ 或 $(x+1, y)$ 的代价为 $A$，移动到 $(x, y-1)$ 或 $(x, y+1)$ 的代价为 $B$。
• 如果 $k$ 为偶数：从 $(x, y)$ 移动到 $(x-1, y)$ 或 $(x+1, y)$ 的代价为 $B$，移动到 $(x, y-1)$ 或 $(x, y+1)$ 的代价为 $A$。

求将棋子移动到坐标 $(X, Y)$ 所需的最小总代价。

输入包含多组数据。

输入格式

T
A_1 B_1 X_1 Y_1
A_2 B_2 X_2 Y_2
...
A_T B_T X_T Y_T

第一行为测试用例数 $T$，接下来 $T$ 行每行四个整数 $A, B, X, Y$。

输出格式

输出共 $T$ 行，第 $i$ 行表示第 $i$ 组数据的最小总代价。

输入示例 1

2
1 2 2 2
5 3 3 5

输出示例 1

4
26

示例 1 说明

第 1 组：$A = 1, B = 2$，目标 $(2, 2)$。

按"右、上、右、上"的顺序移动：

• 第 $1$ 次（奇）向右：代价 $A = 1$；
• 第 $2$ 次（偶）向上：代价 $A = 1$；
• 第 $3$ 次（奇）向右：代价 $A = 1$；
• 第 $4$ 次（偶）向上：代价 $A = 1$。

总代价 $= 4$，达到最小值。

第 2 组：$A = 5, B = 3$，目标 $(3, 5)$。

合理安排顺序，使得尽量多的步骤代价为较小的 $3$。最优策略总代价为 $26$。

输入示例 2

3
10 1 0 3
2 7 4 0
1 1 1000000000 1000000000

输出示例 2

5
16
2000000000

示例 2 说明

• 第 $1$ 组：$X=0, Y=3$，$X+Y$ 为奇数。通过「右-上-左-上-上」等迂回方案，可以让所有 $5$ 步都用代价 $B = 1$，总代价 $5$。
• 第 $2$ 组：$X=4, Y=0$，$X+Y$ 为偶数。若直接走 $4$ 步，奇偶步交替会强制使用 $B = 7$，最少代价为 $2+7+2+7 = 18$。但通过额外 $4$ 步上下蛇形迂回（每次上 + 下回原位），可以让所有 $8$ 步都使用代价 $A = 2$，总代价 $8 \times 2 = 16$。
• 第 $3$ 组：$A = B = 1$，每步代价均为 $1$，曼哈顿距离为 $2 \times 10^9$，总代价 $2 \times 10^9$。

约束条件

• $1 \le T \le 10^5$
• $1 \le A, B \le 10^9$
• $-10^9 \le X, Y \le 10^9$
• 所有输入值均为整数