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.
import sys

def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()


for _ in range(int(input())):
    
    
    x,y = get_ints()
    a,b = get_ints()
    s=0
    # while(x!=0 or y!=0):
    #     if(x>0 and y==0):
    #         s=s+a
    #         x=x-1
    #     elif(x<0 and y==0):
    #         s=s+a
    #         x=x+1
    #     elif(y>0 and x==0):
    #         y=y-1
    #         s=s+a
    #     elif(y<0 and x==0):
    #         s=s+a
    #         y=y+1
    #     elif(x>0 and y<0):
    #         s=s+2*a
    #         x=x-1
    #         y=y+1
    #     elif(x<0 and y>0):
    #         s=s+2*a
    #         x=x+1
    #         y=y-1
    #     else:
    #         if(x>0 and y>0):
    #             if(2*a>b):
    #                 s=s+b
    #                 y=y-1
    #                 x=x-1
    #             else:
    #                 s=s+2*a
    #                 y=y-1
    #                 x=x-1
    #         elif(a<0 and b<0):
    #             if(2*a>b):
    #                 s=s+b
    #                 x=x+1
    #                 y=y+1
    #             else:
    #                 s=s+2*a
    #                 x=x+1
    #                 y=y+1
    # print(s)
    if(x==0 and b==0):
        s=0
    elif(x==0 and y<0):
        s=s+(-1*y)*a
    elif(x==0 and y>0):
        s=s+(y)*a
    elif(x<0 and y==0):
        s=s+(-1*x)*a
    elif(x>0 and y==0):
        s=s+(x)*a
    elif(x>0 and y>0):
        if(x==y):
            if(x*b>2*x*a):
                s=s+2*x*a
            else:
                s=s+x*b
        else:
            if(x>y):
                ma=x
                mi=y
            else:
                ma=y
                mi=x
            if((ma+mi)*a>(mi*b)+(ma-mi)*a):
                s=s+(mi*b)+(ma-mi)*a
            else:
                s=s+(ma+mi)*a
    
    elif(x<0 and y<0):
        x=-1*x
        y=-1*y
        if(x==y):
            if(x*b>2*x*a):
                s=s+2*x*a
            else:
                s=s+x*b
        else:
            if(x>y):
                ma=x
                mi=y
            else:
                ma=y
                mi=x
            if((ma+mi)*a>(mi*b)+(ma-mi)*a):
                s=s+(mi*b)+(ma-mi)*a
            else:
                s=s+(ma+mi)*a
    elif(x>0 and y<0):
        y=-1*y
        if(y*b+(x+y)*a>(x+y)*a):
            s=s+(x+y)*a
        else:
            s=s+y*b+(x+y)*a
    elif(x<0 and y>0):
        x=-1*x
        if(x*b+(x+y)*a>(x+y)*a):
            s=s+(x+y)*a
        else:
            s=s+x*b+(x+y)*a
            
    print(s)
    