Algorithm

A. Road To Zero
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers x and y. You can perform two types of operations:

1. Pay a dollars and increase or decrease any of these integers by 11. For example, if x=0�=0 and y=7�=7 there are four possible outcomes after this operation:
• x=0�=0y=6�=6;
• x=0�=0y=8�=8;
• x=1�=−1y=7�=7;
• x=1�=1y=7�=7.

2. Pay b dollars and increase or decrease both integers by 11. For example, if x=0�=0 and y=7�=7 there are two possible outcomes after this operation:
• x=1�=−1y=6�=6;
• x=1�=1y=8�=8.

Your goal is to make both given integers equal zero simultaneously, i.e. x=y=0�=�=0. There are no other requirements. In particular, it is possible to move from x=1�=1y=0�=0 to x=y=0�=�=0.

Calculate the minimum amount of dollars you have to spend on it.

Input

The first line contains one integer t (1t1001≤�≤100) — the number of testcases.

The first line of each test case contains two integers x and y (0x,y1090≤�,�≤109).

The second line of each test case contains two integers a and b (1a,b1091≤�,�≤109).

Output

For each test case print one integer — the minimum amount of dollars you have to spend.

Example
input
Copy
2
1 3
391 555
0 0
9 4

output
Copy
1337
0

Note

In the first test case you can perform the following sequence of operations: first, second, first. This way you spend 391+555+391=1337391+555+391=1337 dollars.

In the second test case both integers are equal to zero initially, so you dont' have to spend money.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
ll x, y, a, b;
cin>>x>>y>>a>>b;
if(2* a < b){
cout<<(a * x + y * a)<<endl;
continue;
}
else{
cout<<((max(x, y) - min(x, y)) * a + min(x, y) * b)<<endl;
}

}

}
Copy The Code &

Input

cmd
2
1 3
391 555
0 0
9 4

Output

cmd
1337
0