Description

Xiao Y recently encountered a tricky problem. She has two tasks to complete. The first task is to repeat operation 1 (hereinafter referred to as op1) exactly $S_1$ times, and the second task is to repeat operation 2 (hereinafter referred to as op2) exactly $S_2$ times. To complete these tasks, Xiao Y hired $N$ workers. For the $i$-th worker, the time to complete one op1 is $T_{1,i}$, and the time to complete one op2 is $T_{2,i}$. Each op1 and op2 can only be completed by one worker, and each worker can only perform one job at any moment.

All workers start working at time $0$. Whenever a worker starts an operation (op1 or op2), they must continue until it finishes and cannot be interrupted. Let the completion time of the first task be $E_1$, and the completion time of the second task be $E_2$. Your goal is to schedule the workers so that $E_1 + E_2$ is minimized.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains three integers $N, S_1, S_2$ as described above.

Each of the next $N$ lines contains two integers $T_{1,i}, T_{2,i}$, denoting the time the $i$-th worker needs to complete one op1 and one op2, respectively.

Output Format

Output $T$ lines. Each line contains a single integer, the minimum value of $E_1 + E_2$ you can achieve.

4

1 2 3
10 20

3 5 7
10 20
15 16
17 18

4 3 6
10 12
8 9
16 11
13 20

4 4 6
7 12
5 3
6 5
1000000 1000000

100
162
84
41

Hint

Sample Explanation

In the first test case, the only worker first performs op1 $2$ times and finishes task 1 at time $20$ ( $E_1 = 20$ ). Then they perform op2 $2$ times and finish task 2 at time $80$ ( $E_2 = 80$ ). Therefore, the answer is $20 + 80 = 100$.

In the second test case, worker #1 performs op1 $5$ times consecutively and finishes task 1 at time $50$ ( $E_1 = 50$ ). Worker #2 performs op2 $7$ times and finishes task 2 at time $112$ ( $E_2 = 112$ ). Therefore, the answer is $50 + 112 = 162$.

The third test case is similar to the second test case.

In the fourth test case, worker #2 first performs op2 $6$ times and finishes task 2 at time $18$ ( $E_2 = 18$ ). Meanwhile, worker #3 performs op1 $3$ times and also finishes at time $18$. At this point, one more op1 is still needed, so worker #2 performs the last op1 and finishes task 1 at time $23$ ( $E_1 = 23$ ). Therefore, the answer is $18 + 23 = 41$.

Constraints

For $100\%$ of the testdata, $1 \le T \le 7$, $1 \le N \le 100$, $1 \le S_1, S_2 \le 7$, and $1 \le T_{1,i}, T_{2,i} \le 10^6$.

Translated by ChatGPT 5