Captain Kaban

Captain Kaban: National Treasure is a popular football simulation game which can be played on most smartphones. In this game, you put up a team of 11 players and then compete in either story mode or multi-player mode. As you might already know, a football match is played by 11 players, which consists of one goalkeeper and ten outfield players.

Each outfield player's capability is measured with scores in 3 areas: Attack (dribble, shoot, pass), Defense (tackle, block, intercept), and Physical (speed, power, technique). For example, a player with A:4103 D:2837 P:3410 is a typical attacker player (forward position) as his Attack (4103) is higher than his Defense (2837) and Physical (3410). On the other hand, a player with A:1546, D:5209, P:2708 is a typical defensive player as his Defense is much higher than his Attack and Physical. A goalkeeper has a different measurement (Saving and Physical), but it's not our concern in this problem.

A team strength is simply the sum of all the main outfield player's capability-scores. Note that the team strength score does not consider the team's balance, e.g., a team of 10 players where each player has A:8000, D:1000, P:1000 is stronger than a team where each player has A:3000, D:3000, P:3000; the first team's team strength is 100,000 (10 * (8000 + 1000 + 1000)) while the second one is 90,000 (10 * (3000 + 3000 + 3000)).

Let say you are given a team with ten main outfield players and N reserve players. If you are allowed to substitute at most 1 main outfield player (with a reserve player), what is the maximum team strength you can obtain?

For example, let there be ten main outfield players:

 #1 -- A:300  D:200  P:700
 #2 -- A:400  D:600  P:400
 #3 -- A:500  D:400  P:800
 #4 -- A:100  D:100  P:700
 #5 -- A:600  D:200  P:600
 #6 -- A:800  D:300  P:100
 #7 -- A:200  D:900  P:100
 #8 -- A:900  D:400  P:900
 #9 -- A:900  D:300  P:200
#10 -- A:700  D:200  P:400
---------------------------
TOTAL  A:5400 D:3600 P:4900  =  13900 (team strength)

And 3 reserve players:

 $1 -- A:400  D:900  P:600
 $2 -- A:800  D:200  P:100
 $3 -- A:100  D:100  P:700

If you substitute #4 (A:100 D:100 P:700) with $1 (A:400 D:900 P:600), then the team strength will be 13900 - (100 + 100 + 700) + (400 + 900 + 600) = 14900. This is the best substitution you can make in this example.

Input

Input begins with an integer: T (1 ≤ T ≤ 20) denoting the number of cases.

Each case contains the following input block: Each case begins with an integer: N (1 ≤ N ≤ 10) denoting the number of reserve players. The next 10 lines each contains three integers: Ai Di Pi (100 ≤ Ai, Di, Pi ≤ 20,000) representing the Attack, Defense, and Physical score for the ith main player. The next N lines each contains three integers: Aj Dj Pj (100 ≤ Aj, Dj, Pj ≤ 20,000) representing the Attack, Defense, and Physical score for the jth reserve player.

Output

For each case, output in a line "Case #X: Y" where X is the case number (starts from 1) and Y is the output for the respective case.

Examples

inputExample #1
3
3
300 200 700
400 600 400
500 400 800
100 100 700
600 200 600
800 300 100
200 900 100
900 400 900
900 300 200
700 200 400
400 900 600
800 200 100
100 100 700
5
1644 2815 1136
1463 1523 2148
2157 2004 1121
2303 1920 1272
1299 2855 2037
2061 1825 1882
1096 2162 1855
2269 2358 1062
1313 2989 2086
1324 1327 2958
1214 2271 2110
1821 1009 2965
2536 1983 2820
2873 2387 2895
2414 2734 1652
4
4000 4600 5000
3100 4200 4200
4000 3500 4500
3300 4200 3400
3400 3200 4300
4600 4500 4300
3300 3400 4800
5000 4000 3900
4600 4200 3300
4200 4500 3000
2400 1900 1100
1600 1500 1500
1200 1700 1800
2700 2500 1400
output
Case #1: 14900
Case #2: 59306
Case #3: 120500
explanation

Case 1: This is the example given in the problem statement.

Case 2: The original team strength is 56264, while the fourth reserve player has the highest score of 8155 (2873 + 2387 + 2895) and the seventh main player has the lowest score of 5113 (1096 + 2162 + 1855). Thus, substituting the seventh main player with the fourth reserve player will make the team strength to be 56264 - 5113 + 8155 = 59306.

Case 3: All the reserve players are weaker than the main players, thus, no substitution is needed. The original team strength is 120500.



End of Problem