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 java.util.*;
import java.io.*;
import java.util.stream.*;

public class Main{
	private static BufferedReader in;
	private static BufferedWriter out;
	
	public static void main(String[] args) throws IOException {
		open();

		StringTokenizer st;
		StringBuilder sb;
		
		int t=readInt();
		long x,y,a,b,suma1,suma2,minimo;
		while(t-->0) {
			st=new StringTokenizer(readString());
			x=Long.parseLong(st.nextToken());
			y=Long.parseLong(st.nextToken());
			st=new StringTokenizer(readString());
			a=Long.parseLong(st.nextToken());
			b=Long.parseLong(st.nextToken());
			suma1=0;suma2=0;
			suma1=(x+y)*a;
			minimo=Math.min(x, y);
			suma2=(minimo)*b;
			minimo=Math.max(x, y)-minimo;
			suma2+=minimo*a;
			out.write(Math.min(suma1, suma2)+"\n");
		}
		close();
	}
	
	private static int[] readInts() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
	}

	private static int readInt() throws IOException {
		return Integer.parseInt(in.readLine());
	}

	private static long[] readLongs() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
	}

	private static long readLong() throws IOException {
		return Long.parseLong(in.readLine());
	}

	private static double[] readDoubles() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToDouble(Double::parseDouble).toArray();
	}

	private static double readDouble() throws IOException {
		return Double.parseDouble(in.readLine());
	}

	private static String readString() throws IOException {
		return in.readLine();
	}

	private static int setBit(int S, int j) {
		return S | (1 << j);
	}

	private static int isOn(int S, int j) {
		return S & (1 << j);
	}

	private static int clearBit(int S, int j) {
		return S & ~(1 << j);
	}

	private static int toggleBit(int S, int j) {
		return S ^ (1 << j);
	}

	private static int lowBit(int S) {
		return S & (-S);
	}

	private static int setAll(int n) {
		return (1 << n) - 1;
	}

	private static int modulo(int S, int N) {
		return ((S) & (N - 1));
	} // returns S % N, where N is a power of 2

	private static boolean isPowerOfTwo(int S) {
		return (S & (S - 1)) == 0 ? true : false;
	}

	private static int nearestPowerOfTwo(int S) {
		return ((int) Math.pow(2.0, (int) ((Math.log((double) S) / Math.log(2.0)) + 0.5)));
	}

	private static int turnOffLastBit(int S) {
		return ((S) & (S - 1));
	}

	private static int turnOnLastZero(int S) {
		return ((S) | (S + 1));
	}

	private static int turnOffLastConsecutiveBits(int S) {
		return ((S) & (S + 1));
	}

	private static int turnOnLastConsecutiveZeroes(int S) {
		return ((S) | (S - 1));
	}

	private static void open() {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new BufferedWriter(new OutputStreamWriter((System.out)));
	}

	private static void close() throws IOException {
		out.flush();
		out.close();
		in.close();
	}
}
