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.
# s1=list(map(int,input().split()))		


# t = int(input())

# for _ in range(t):
# 	n = int(input())
# 	# s1=list(map(int,input().split()))
# 	s1 = input()
# 	s1 = str(s1)	

# 	temp = 0

# 	a=[]
# 	b=[]

# 	for i in range(n):
# 		if s1[i]=='0':
# 			a.append(0)
# 			b.append(0)
# 		elif s1[i]=='2':
# 			a.append(1)
# 			b.append(1)
# 		else:
# 			if(temp==0):
# 				a.append(1)
# 				b.append(0)
# 				temp = 1
# 			else:
# 				a.append(0)
# 				b.append(1)
# 				temp = 0
						


	
# 	print(a)
# 	print(b)					


# print(0)



# A = [1,2,3,4,5,5]

# m1 = -1000
# m2 = -1000
# temp = 0
# for i in A:
#     if temp>=0:
#         print(i)
#         temp = temp+i
#         print(temp)
#         if(temp>m2):
#             m2 = temp
#     else:
#         temp = i
		

# print(m2)       



# def reverse_Bits(n):
#   result = 0
#   for i in range(32):
#       result <<= 1
#       result |= n & 1
#       n >>= 1
#   return result
			
# print(reverse_Bits(1234))




# inp = input()


# print(inp)

# l = len(inp)
# get_bin = lambda x, n: format(x, 'b').zfill(n)

# for i in inp:
#   temp = get_bin(int(i), 32)
#   print(reverse_Bits(10)
  
  
# t = int(inut())
# for _ in range(t):
# 	s1=list(map(int,input().split()))  
# 	a = []
# 	index = []
# 	for i in range(len(s1)-1):

# 		a.append(s1[i]-s1[i+1])
# 		index.append(i)

# 	zipped = list(zip(a,index))
# 	result = sorted(zipped, key = lambda x: x[1]) 	




# t = int(input())
# for _ in range(t):
# 	# t1 = int(input())
# 	s1=list(map(int,input().split()))  
# 	x = s1[0]
# 	n = s1[1]
# 	m = s1[2]
# 	ans = 0
# 	if(x<=0):
# 		ans = 1
# 	else:
# 		while(x>=20 and n>0):
# 			x = x//2+10
# 			# print(x)
# 			n-=1
# 			if(x<=0):
# 				ans = 1
# 				# print('YES')
				
# 		while(m>0):
# 			x= x-10
# 			m = m-1
# 			# print(x)
# 			if(x<=0):
# 				ans = 1
# 				# print('YES')
# 				# return
	
# 	if ans==1:
# 		print('YES')
# 	else:
# 		print("NO")				



	
		


	# print(d)			



# def detectLoop(head):
#     #code here
	
#     slow = head
#     fast = head
#     ans = 0
#     while slow != None and fast != None and ans = 0 :
#         slow = slow.next
#         fast = fast.next.next
		
#         if(slow == fast):
#             ans = 1
		
	
#     return ans        









#code

# t = int(input())
# for _ in range(t):
# 	# t1 = int(input())
# 	t1 = int(input())
# 	s1=list(map(int,input().split()))   
# 	stack = []
# 	ans=[]
# 	for i in range(t1-1,-1,-1):
# 		if(len(stack)==0):
# 			ans.insert(0,-1)
# 			stack.append(s1[i])
# 		else:
# 			while(len(stack)>0):
# 				if(s1[i]>stack[-1]):
# 					stack.pop(-1)
# 				else:
# 					break
# 			if(len(stack)==0):
# 				ans.insert(0,-1)
# 				stack.append(s1[i])
# 			else:     
# 				ans.insert(0,stack[-1])
# 				stack.append(s1[i])
	  
# 	print(ans)           
				
		
		
# 	




# t=list(map(int,input().split()))		
# s=list(map(int,input().split()))		
 
# temp = 0
# for i in s:
#   temp += i

# # print(temp)
# if(t[0]-temp>=0):
#   print([0]-temp)
# else:
#   print(-1)



# t = int(input())

# for i in range(t):
# 	n = int(input())
# 	# print(s)
# 	s=list(map(int,input().split()))		


# 	ans = []
	

# 	i = 0
# 	while i < len(s):
# 		if s[i] < 0:
# 			max1 = s[i]
# 			# print(s[i])
# 			# print(i)
# 			while s[i] < 0 and i < n:
# 				# print(i)

# 				if(s[i]>max1):
# 					max1 = s[i]
				
# 				i += 1
# 				if i == n:
# 					break
# 			ans.append(max1)
			
# 		else:
# 			max1 = s[i]
# 			while s[i] > 0  and i < n:
# 				if(s[i]>max1):
# 					max1 = s[i]
# 				i += 1
# 				if i == n:
# 					break
# 			ans.append(max1)
			

# 	print(sum(ans))



	
# t = int(input())

# for i in range(t):
# 	n=list(map(int,input().split()))		
	
# 	s=list(map(int,input().split()))		


# 	doc = {}
# 	ans = 0

# 	for i in range(n[0]//2):
# 		k = s[i]+s[n[0]-i-1]
# 		if(k not in doc):
# 			doc[k] = 1
# 		else:
# 			doc[k] +=1


# 	# print(doc)			
# 	ka=[]
# 	k = max(doc.items())
# 	k = k[1]
# 	for i in doc:
# 		if doc[i] == k:
# 			ka.append(i)
# 	# print(k)
# 	# print(ka)
# 	# if(len(ka)>1):
# 	# 	k = n[1]+1
# 	# else:
# 	k = sum(ka)//len(ka)	
# 	# k = min(i for i in ka if i >= n[1])
# 	for i in range(n[0]//2):
# 		t1 = s[i]
# 		t2 = s[n[0]-i-1]
# 		# print(t1,t2)
# 		if(t1+t2==k):
# 			ans = ans
# 		else:
# 			if(t1+t2<k):
# 				if(max(t1,t2)+n[1]>=k):
# 					ans += 1
# 				else:
# 					ans+=2	
# 			else:
# 				if(min(t1,t2)+0<=k):
# 					ans+=1
# 				else:
# 					ans+=2

# 	print(ans)							

# 			



# t = int(input())

# for _ in range(t):
# 	n = int(input())
# 	s = list(map(int,input().split()))

# 	fmin = 1
# 	fminindex = n
# 	falg = True

# 	while(i<=n):
# 		if(s[i-1] == fmin):
# 			temp = s[i-1]
# 			t2 = 0
# 			while(i<=fminindex):
# 				if(s[i-1]!=temp+t2):
# 					falg = False
# 				t2 += 1
# 				i = i+1
					
	



t = int(input())

for _ in range(t):
	# n = int(input())
	m,n = map(int,input().split())
	a,b = map(int,input().split())
	ans = 0
	if(b>2*a):
		ans  = (m+n)*a
	else:
		ans = min(m,n)*b + (max(m,n)-min(m,n))*a

	print(ans)	




