Limits 1s, 512 MB

You brought CC chocolates to a party where there are AA adults and KK kids. You know that an adult will always eat the chocolate fully and a kid will always eat the chocolate partially. For each chocolate, you know how much happiness it brings to one who eats fully or partially. You want to give everyone exactly one chocolate so that the total happiness they get is maximized.

Input

The first line contains one integer TT - the number of test cases. For each test case, the first line contains 3 integers CC, AA, and KK denoting the number of chocolates, adults, and kids respectively. For the next CC lines, ithi’th line contains two integers FiF_i and PiP_i, denoting the happiness one gets if he eats the ithi’th chocolate fully and partially respectively.

1T1061 \leq T \leq 10^6,
1C1051 \leq C \leq 10^5,
0A,K1050 \leq A, K \leq 10^5,
A+KCA + K \leq C,
0PiFi1090 \leq P_i \leq F_i \leq 10^9,

The sum of CC over all test cases does not exceed 10610^6

Output

For each test case, output in a line, the maximum sum of happiness they get. See sample for details.

Sample

InputOutput
2
2 1 1
30 12
20 1
3 1 1
20 10
12 10
15 15
32
35

Submit

Login to submit.

Statistics

48% Solution Ratio
Jarif_RahmanEarliest, Aug '22
AMDAD_MBSTUFastest, 0.0s
AMDAD_MBSTULightest, 11 kB
MrBrionixShortest, 965B
Toph uses cookies. By continuing you agree to our Cookie Policy.