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.
from math import factorial as fac
from collections import defaultdict
from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
sys.setrecursionlimit(10**6)


def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())

NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
from collections import deque, defaultdict 
import heapq

def bfs(V, E):
	s = set()
	print('\n'.join(map(str,E.items())))
	cnt = 0 
	for v in V:
		if v in s:
			continue
		q = deque([])
		s.add(v)
		q.append(v)
		while len(q) > 0:
			x = q.popleft()
			for e in E[x]:
				if e not in s:
					s.add(e)
					q.append(e)
			print(q)
		cnt += 1
	return cnt
		
from typing import List, Tuple

def regular_bs(L,x,l=None,r=None):
	l = 0 if l == None else l
	r = len(L) if r == None else r
	while (r-l) > 1:
		m = (r+l)//2
		l = m if L[m] <= x else l
		r = m if L[m] > x else r
	cnt = 0
	return l

def binary_count_smaller(L, x):
	l = 0
	if x < L[0]:
		return 0
	r = len(L)
	while r - l > 1:
		mid = (l+r)//2
		if L[mid] < x:
			l = mid
		else:
			r = mid
	return l + 1
def binary_count_larger(L, x):
	l = 0
	if x > L[-1]:
		return 0
	r = len(L)
	while r - l > 1:
		mid = (l+r)//2
		if L[mid] <= x:
			l = mid
		else:
			r = mid
	return len(L) - (r-1)

from itertools import product

def solution(x,y,a,b):
	if x*y < 0:
		return a*(abs(x) + abs(y))
	x = abs(x)
	y = abs(y)
	res = a * (max(x,y) - min(x,y))
	if b > 2*a:
		return res + min(x,y) * 2 * a
	return res + min(x,y) * b


def main():
	T = read_int()
	for i in range(T):
		x,y = read_int_array()
		a,b = read_int_array()
		print(solution(x,y,a,b))


if __name__ == '__main__':
	main()
# print(regular_bs([1,2],1))