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.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.Vector;

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.pow;
import static java.lang.Math.abs;
import static java.util.Arrays.sort;
import static java.util.Arrays.parallelSort;
import static java.util.Arrays.binarySearch;

public class cf {
    static final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    static final int mod = (int) (1e9 + 7);
    static final int modf = 998244353;
    static final Reader r = new Reader();
    static final PrintWriter out = new PrintWriter((new BufferedOutputStream(System.out)));
    int[] level, p;
    Vector<Integer>[] adj;

    public static void main(final String[] args) throws Exception {
        final int testcases = hasTestCases ? r.nextInt() : 1;
        for (int i = 0; i < testcases; i++) {
            final long an = new cf().solve();
            if (hasPrint)
                if (hasBooleanPrint)
                    out.println(an == 0 ? "no" : "yes");
                else
                    out.println(an);
            // out.print("Case "+i+1+": ");
        }
        out.flush();
    }

    static final boolean hasTestCases = true, fastIO = true;
    static final boolean hasPrint = true, hasBooleanPrint = false;
    static final int lineLength = 1000002;

    private long solve() throws Exception {
        long x=ni(),y=ni(),a=ni(),b=ni();
        if (x==y&&x==0) {
            return 0;
        }
        if (2*a<b) {
            return x*a+a*y;
        }else{
            return abs(x-y)*a+b*(max(x, y)-abs(y-x));
        }
        // return 1;
    }

    static int gcd(final int a, final int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static String n() throws Exception {
        return fastIO ? r.next() : in.next();
    }

    static String nln() throws Exception {
        return fastIO ? r.nextLine() : in.nextLine();
    }

    static int ni() throws Exception {
        return fastIO ? r.nextInt() : in.nextInt();
    }

    static long nl() throws Exception {
        return fastIO ? r.nextLong() : in.nextLong();
    }

    static double nd() throws Exception {
        return fastIO ? r.nextDouble() : in.nextDouble();
    }

    static void p(final Object o) {
        out.print(o);
    }

    static void pn(final Object o) {
        out.println(o);
    }

    static void pni(final Object o) {
        out.println(o);
        out.flush();
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 19;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        private StringTokenizer st;
        private final BufferedReader br;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public Reader(final String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            br = new BufferedReader(new FileReader(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String next() throws Exception {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (final IOException e) {
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        public String nextLine() throws Exception {
            String str = "";
            try {
                str = br.readLine();
            } catch (final IOException e) {
                throw new Exception(e.toString());
            }
            return str;
        }

        public String readLine() throws IOException {
            final byte[] buf = new byte[lineLength]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

}