Description

You have $a$ candies and $b$ cookies. In each operation, you can perform one of the following two actions:

• Choose either two candies or two cookies and delete them, costing $x$. (You must ensure there are at least two candies or two cookies to perform this operation.)

• Choose one candy and one cookie and delete them, costing $y$. (You must ensure there is at least one candy and one cookie to perform this operation.)

Find the minimum total cost to delete all candies or all cookies (or both).

Input Format

Multiple test cases. The first line of input contains an integer $T$ representing the number of test cases. For each test case:

Input one line containing four positive integers $a$, $b$, $x$, $y$.

Output Format

For each test case, output one integer representing the minimum cost.

3
4 4 10 1
10 5 5 3
2024 1226 32423 23423

4
13
19875299

Hint

Explanation #1

Sample 1 Explanation:

• For the first test case, use the second operation 4 times to delete all candies and cookies, costing $1 \times 4 = 4$.

• For the second test case, use the first operation twice on cookies, then use the second operation once to delete all cookies, costing $5 \times 2 + 3 \times 1 = 13$.

Constraints

For all test cases: $1 \le T \le 10$, $1 \le a, b, x, y \le 10^5$.

Translated by DeepSeek R1