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.
_IS_DEBUG_MODE = False



def Problem():
    # use custom test cases when debug mode
    if _IS_DEBUG_MODE == True:
        testcaseList = []
        testcaseList.append([1, 3, 391, 555])
        testcaseList.append([0, 0, 9, 4])
        testcaseList.append([30, 10, 2, 1])
        testcaseList.append([1000000, -100000, 9, 4])
        
    else:
        # input number of test cases
        t = int(input())
        
        # repeat input test cases
        testcaseList = []
        for testcaseIndex in range(t):
            # input test case
            x, y = list(map(int, input().split()))
            a, b = list(map(int, input().split()))
            testcaseList.append([x, y, a, b])
    
    return testcaseList



def Solver(testcaseList):
    # repeat calc answer
    for x, y, a, b in testcaseList:
        if _IS_DEBUG_MODE == True:
            print('testcase', x, y, a, b)
        
        costList = []
            
        # type 1: use a only
        cost = (abs(x) + abs(y)) * a
        costList.append(cost)
        
        # type 2: make x = 0 by b, and use a
        cost = abs(x) * b + abs(y - x) * a
        costList.append(cost)
        
        cost = abs(y) * b + abs(x - y) * a
        costList.append(cost)
        
        # type 3
        cx_float = float(x - y) / 2.0
        #cy = float(y - x) / 2.0
        dxy = int(cx_float - x)
        cx = x + dxy
        cy = y + dxy
        
        cost = abs(dxy) * b + (abs(cx) + abs(cy)) * a
        costList.append(cost)
        
        dxy += 1
        cx = x + dxy
        cy = y + dxy
        
        cost = abs(dxy) * b + (abs(cx) + abs(cy)) * a
        costList.append(cost)
        
        dxy -= 1
        cx = x + dxy
        cy = y + dxy
        
        cost = abs(dxy) * b + (abs(cx) + abs(cy)) * a
        costList.append(cost)
        
        if _IS_DEBUG_MODE == True:
            print(costList)
        
        print(min(costList))
        
        

if __name__ == '__main__':
    # time check when debug mode
    if _IS_DEBUG_MODE == True:
        import time
        
        startTime = time.time()
    
    # problem solving
    testcaseList = Problem()
    Solver(testcaseList)
    
    # time check when debug mode
    if _IS_DEBUG_MODE == True:
        endTime = time.time()
        
        print('time', endTime - startTime)
        