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.
// Working program with FastReader 
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.LinkedList; 
import java.util.StringTokenizer; 

public class Main 
{ 

    
    public static void main(String[] args) 
	{ 
		FastReader sc=new FastReader(); 
		int test=sc.nextInt();
		while(test-->0){
		    long x=sc.nextLong();
		    long y=sc.nextLong();
		    long a=sc.nextLong();
		    long b=sc.nextLong();
		    long ans=0l;
		    if(x == 0 || y==0){
		            ans+=Math.abs(a*y)+Math.abs(a*x);
		       System.out.println(ans);
		       continue;
		    }
		    if(x>0 && y<0 || x<0 && y>0){
		       ans+=Math.abs(a*y)+Math.abs(a*x);
		       System.out.println(ans);
		        continue;    
		    }
		    
		    if(x>0 && y>0){
		        if(a*2 >= b){
    		        long count=Math.min(x,y);
    		        ans+=(count*b);
    		        x-=count;
    		        y-=count;
    		    }
    		    
    		    if(x>0) ans+=(x*a);
    		    if(y>0) ans+=(y*a);
		    }
		    else if(x<0 && y<0){
		         if(a*2 >= b){
    		        long count=Math.max(x,y)*-1;
    		        ans+=(count*b);
    		        x+=count;
    		        y+=count;
    		    }
    		      if(x<0) ans+=(x*a*-1);
    		      if(y<0) ans+=(y*a*-1);
		    }
		    System.out.println(ans);
		    
		    
		    
		    
		    
		    
		}
		
	
	} 
	
	static class FastReader 
	{ 
		BufferedReader br; 
		StringTokenizer st; 

		public FastReader() 
		{ 
			br = new BufferedReader(new
					InputStreamReader(System.in)); 
		} 

		String next() 
		{ 
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken(); 
		} 

		int nextInt() 
		{ 
			return Integer.parseInt(next()); 
		} 

		long nextLong() 
		{ 
			return Long.parseLong(next()); 
		} 

		double nextDouble() 
		{ 
			return Double.parseDouble(next()); 
		} 

		String nextLine() 
		{ 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		} 
	} 


} 
