Score : 500 points
We have N camels numbered 1,2,\ldots,N. Snuke has decided to make them line up in a row.
The happiness of Camel i will be L_i if it is among the K_i frontmost camels, and R_i otherwise.
Snuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.
Solve this problem for each of the T test cases given.
Input is given from Standard Input in the following format:
T \mathrm{case}_1 \vdots \mathrm{case}_T
Each case is given in the following format:
N K_1 L_1 R_1 \vdots K_N L_N R_N
Print T lines. The i-th line should contain the answer to the i-th test case.
3 2 1 5 10 2 15 5 3 2 93 78 1 71 59 3 57 96 19 19 23 16 5 90 13 12 85 70 19 67 78 12 16 60 18 48 28 5 4 24 12 97 97 4 57 87 19 91 74 18 100 76 7 86 46 9 100 57 3 76 73 6 84 93 1 6 84 11 75 94 19 15 3 12 11 34
25 221 1354