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 1. For example, if x = 0 and y = 7 there are four possible outcomes after this operation: 
    * x = 0, y = 6; 
    * x = 0, y = 8; 
    * x = -1, y = 7; 
    * x = 1, y = 7. 

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



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

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

Input

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

The first line of each test case contains two integers x and y (0 ≤ x, y ≤ 10^9).

The second line of each test case contains two integers a and b (1 ≤ a, b ≤ 10^9).

Output

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

Example

Input


2
1 3
391 555
0 0
9 4


Output


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 = 1337 dollars.

In the second test case both integers are equal to zero initially, so you dont' have to spend money.
# cook your dish here
import math,sys
import heapq
from fractions import Fraction
from collections import Counter,defaultdict
def li(): return list(map(int,sys.stdin.readline().split()))
def ls(): return list(map(int,list(input())))
def la(): return list(input())
def ii():  return int(input())
def dic(x): return defaultdict(lambda: x) 
def isPrime(n):
    i= 2
    if n == 1:
        return False
    while i <= int(math.sqrt(n)):
        if n%i == 0:
            return False
        i = i + 1
    return True
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def binarySearch(arr, x): 
    l,r = 0,len(arr)-1
    while l <= r: 
        mid = l + (r - l) // 2; 
        if arr[mid] == x: 
            return True 
        elif arr[mid] < x: 
            l = mid + 1
        else: 
            r = mid - 1
    return False
t = ii()
for _ in range(t):
    x,y = li()
    a,b = li()
    total = abs(x-y)*a
    if (min(x,y)*2)*a<b*(min(x,y)):
        total += (min(x,y)*2)*a
    else:
        total += b*(min(x,y))
    print(total)

