You are given two integers $x$ and $y$. You can perform two types of operations:   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$. 

  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 \le t \le 100$) — the number of testcases.

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

The second line of each test case contains two integers $a$ and $b$ ($1 \le a, b \le 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.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	x,y = map(int,input().split())
	a,b = map(int,input().split())
	wynik = 0
	if b <= 2*a:
		c = min(x,y)
		wynik += b*c
		wynik += (max(x,y)-c)*a
	else:
		wynik = a*(x+y)
	print(wynik)

t = int(input())
for q in range(0, t):
    x, y = list(map(int, input().split()))
    a, b = list(map(int, input().split()))
    print(min(b * min(x, y) + a * (max(x, y) - min(x, y)), (x + y) * a))


for _ in range(int(input())):
    x, y = list(map(int, input().split()))
    a, b = list(map(int, input().split()))
    ans = a * abs(x - y)
    if a * 2 < b:
        ans += min(x, y) * a * 2
    else:
        ans += min(x, y) * b
    print(ans)

def solve(x, y, a, b):
    if b >= a * 2:
        return (x + y) * a
    else:
        return min(x, y) * b + (max(x, y) - min(x, y)) * a
[print(solve(*map(int, input().split()), *map(int, input().split()))) for _ in range(int(input()))]

for _ in range(int(input())):
    x, y = tuple(map(int, input().split()))
    a, b = tuple(map(int, input().split()))

    if a * 2 <= b:
        print((x + y) * a)
    else:
        print(min(x, y) * b + (max(x, y) - min(x, y)) * a)


def solve():
    x, y = map(int, input().split())
    a, b = map(int, input().split())
    d = abs(x - y)
    a1 = a * (x + y)
    a2 = b * min(x, y) + a * d
    print(min(a1, a2))

for i in range(int(input())):
    solve()



for _ in range(int(input())):
	x,y=map(int,input().split())
	a,b=map(int,input().split())

	common=min(x,y)

	if(2*common*a<=common*b):
		print(x*a+y*a)
	else:
		print(common*b+(max(x,y)-common)*a)

LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
yes = lambda: print("Yes")
no = lambda: print("No")
I = lambda: list(input())
J = lambda x: "".join(x)
II = lambda: int(input())
SI = lambda: input()
#---khan17---template
t = II()
for i in range(t):
	x,y = MI()
	a,b = MI()
	if b>2*a:
		print((x+y)*a)
	else:
		c = abs(x-y)*a+min(x,y)*b
		print(c)


for i in range(int(input())):
    x,y=map(int,input().split())
    a,b=map(int,input().split())
    b=min(2*a,b)
    mi=min(x,y)
    ma=max(x,y)
    ans=mi*b+(ma-mi)*a
    print(ans)

from math import inf
t = int(input())
for q in range(t):
    x, y = [int(i) for i in input().split()]
    a, b = [int(i) for i in input().split()]
    print(min(a * (x + y), a * abs(x - y) + b * min(x, y)))


t = int(input())
for _ in range(t):
    x, y = map(int, input().split())
    a, b = map(int, input().split())
    ans = min(b*min(x, y) + a * abs(x-y), a*(x+y))
    print(ans)

t = int(input())
for i in range(t):
    x, y = list(map(int, input().split()))
    a, b = list(map(int, input().split()))
    if 2 * a >= b:
        print(min(x, y) * b + (x + y - 2 * min(x, y)) * a)
    else:
        print((x + y) * a)


t=int(input())
for _ in range(t):
    x,y=list(map(int,input().split()))
    a,b=list(map(int,input().split()))
    cst=0
    if(2*a>b):
        cst+=b*min(x,y)
        e=min(x,y)
        x-=e
        y-=e
    cst+=a*x+a*y
    print(cst)


T = int(input())
for _ in range(T):
    x, y = list(map(int, input().split()))
    if x < y: x, y = y, x
    a, b = list(map(int, input().split()))
    if b < a * 2:
        print(b * y + a * (x - y))
    else:
        print(a * (x + y))


from math import *


def solve():
    x, y = list(map(int, input().split()))
    a, b = list(map(int, input().split()))

    mn = min(abs(x), abs(y))
    ans = 0
    if b < 2 * a:
        ans += b * (mn)
        if x == mn:
            x = 0
            if y > 0:
                y -= mn
            else:
                y += mn
            ans += a * abs(y)
            print(ans)
        else:
            y = 0
            if x > 0:
                x -= mn
            else:
                x += mn
            ans += a * abs(x)
            print(ans)
    else:
        print(a * (abs(x) + abs(y)))


for _ in range(int(input())):
    solve()