Little Y has recently encountered a tricky problem. She has two tasks to complete: the first task is to repeat operation $op_1$ $S_1$ times, and the second task is to repeat operation $op_2$ $S_2$ times. To complete these tasks, Little Y has hired $N$ workers. For each worker $i$, the time required to complete $op_1$ is $T_{1,i}$, and the time required to complete $op_2$ is $T_{2,i}$. Each $op_1$ and $op_2$ must be completed by exactly one worker, and each worker can only perform one job at any given time.

All workers start working at time $0$. Whenever a worker begins an operation ($op_1$ or $op_2$), they must continue until it is finished and cannot be interrupted. Let $E_1$ be the time the first task is completed, and $E_2$ be the time the second task is completed. Your task is to schedule the work of these employees such that $E_1 + E_2$ is minimized.

Input

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

The first line of each test case contains three integers $N$, $S_1$, and $S_2$, as described above.

The next $N$ lines each contain two integers $T_{1,i}$ and $T_{2,i}$, representing the time required for the $i$-th worker to complete $op_1$ and $op_2$, respectively.

Output

The output file contains $T$ lines, each containing a single integer representing the minimum value of $E_1 + E_2$ you found.

Constraints

For 100% of the data, $1 \le T \le 7$, $1 \le N \le 100$, $1 \le S_1, S_2 \le 7$, $1 \le T_{1,i}, T_{2,i} \le 1000000$.

Examples

Input 1

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

Output 1

100
162
84
41

Note

In the first test case, the only worker first performs $op_1$ 2 times, completing the first task at 20 seconds ($E_1=20$). Then they perform $op_2$ 2 times, completing the second task at 80 seconds ($E_2=80$). Thus, the answer is $20+80=100$.

In the second test case, worker #1 performs $op_1$ 5 times consecutively, completing the first task at 50 seconds ($E_1=50$), and worker #2 performs $op_2$ 7 times, completing the second task at 112 seconds ($E_2=112$). Thus, the answer is $50+112=162$.

The third test case is similar to the second.

In the fourth test case, worker #2 first performs $op_2$ 6 times consecutively, completing the second task at 18 seconds ($E_2=18$). At the same time, worker #3 performs $op_1$ 3 times, also completing at 18 seconds. At this point, one more $op_1$ still needs to be performed, so worker #2 is assigned to perform the final $op_1$, completing the first task at 23 seconds ($E_1=23$). Thus, the answer is $18+23=41$.