jobs

In a factory, there are 2 jobs which need to be executed. The first job consists of the execution of S₁ consecutive identical steps. The second job consists of the execution of S₂ consecutive identical steps. There are N persons working in this factory and each person may execute any step of any of the 2 jobs. For each person K, it is known the duration T_1K needed to execute a step of the first job and the duration T_2K needed to execute a step of the second job. Each step of the 2 jobs must be executed by exactly one person. The same person may execute multiple steps from both jobs. However, a person can only execute one step at a given moment in time.
The execution of the 2 jobs is considered to begin early in the morning, after all the N workers have arrived at the factory (that is, at time 0). Once a worker has started executing a step of one of the jobs, that worker cannot be interrupted until the execution of that step ends. Interruptions may occur, however, before the beginning of the execution of each step: that is, you may have waiting times before the beginning of the execution of any step of any of the 2 jobs.
Let's consider the moment T_J1 when the execution of the last step of the first job ends and the moment T_J2, when the execution of the last step of the second job ends. The manager of the factory is interested in minimizing the sum TJ₁ + TJ₂.

Task

Write a program to determine the minimum possible value for the sum TJ₁ + TJ₂.

Input data

The first line of the input file jobs.in contains the number of input data sets T. The next lines describe the T data sets. The first line of each data set contains 3 positive integers numbers, separated by blanks N S1 S2 , representing the number of persons working at the factory, the number of steps of the first job and the number of steps of the second job. The following N lines contain 2 integer each : T1K and T2K. There will be a blank line before each test case.

Output data

For each of the T data sets in the input file, you must print in the output file jobs.out a line containing the minimum value of the sum TJ1 + TJ2.

Restrictii si precizari

1 <= T <= 20
1 <= N <= 100
1 <= S₁ <= 7
1 <= S₂ <= 7
1 <= T_1K <= 1.000.000
1 <= T_2K <= 1.000.000

Example

jobs.in

jobs.out

Explanation

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

In the first data set, the one and only worker executes the first 2 steps of the first job and finishes at time 20 (TJ₁ = 20). Then, starting at time 20, he executes the 3 steps of the second job, finishing at time 80 (TJ₂ = 80). So the answer is 20 + 80 = 100.

In the second data set, worker #1 executes all the 5 steps of the first job, finishing at time 50, and worker #2 executes all the 7 steps of the second job, finishing at time 112. So the answer is 50 + 112 = 162.

In the third data set, worker #1 executes all the 3 steps of the first job, finishing at time 30, and worker #2 executes all the 6 steps of the second job, finishing at time 54. So the answer is 30 + 54 = 84.

In the fourth data set, worker #2 executes all the 6 steps of the second job, finishing at time 18 (TJ₂ = 18). Starting from time 0, worker #3 executes the first 3 steps of the first job, finishing at time 18 (what a coincidence J). Then, the 4^th step of the first job is executed by the 2^nd worker, from time 18 until time 23 (TJ₁ = 23). So the answer is 18 + 23 = 41.

Time limit: 0.1 seconds/test

Mugurel Ionut Andreica
Politehnica University Bucuresti
Contact:mugurel_ionut@yahoo.com