Battlefield (Large)

After the Third World War most modern technology was gone and only a few people survived. Humanity rebuilt slowly and started a new history. Thousands of years later, in a new medieval age, General Kim Yushin faced an enemy general on the battlefield.

Kim Yushin commands $N$ officers. $A$ of them carry weapon 1, $B$ carry weapon 2, and $C$ carry weapon 3. They stand side by side in one long line on a hill, looking at the enemy camp.

The enemy general also commands $N$ officers. $D$ of them carry weapon 4, $E$ carry weapon 5, and $F$ carry weapon 6. They form one line on the opposite hill and prepare to hold off the attack.

Once the battle starts, the two lines face each other in the order they stand, and each pair fights one on one. Before giving the order to attack, Kim Yushin can rearrange his own line in any order he likes.

You are given the integers $P_{14}$, $P_{15}$, $P_{16}$, $P_{24}$, $P_{25}$, $P_{26}$, $P_{34}$, $P_{35}$, $P_{36}$. $P_{ij}$ is the result of the duel when an officer of Kim Yushin carrying weapon $i$ meets an enemy officer carrying weapon $j$. A positive value means a result in Kim Yushin's favor.

The result of the whole battle is the sum of the results of the single duels. Find the largest total battle result Kim Yushin can reach by rearranging his line.

The first line contains the number of test cases $T$. Each test case is given on the following four lines.

N A B C D E F
P14 P15 P16
P24 P25 P26
P34 P35 P36

Constraints

• All values are integers.
• $1 \le T \le 1000$
• $1 \le N \le 10^{13}$
• $0 \le A, B, C, D, E, F \le N$
• $A + B + C = N$
• $D + E + F = N$
• $-100000 \le P_{14}, P_{15}, P_{16}, P_{24}, P_{25}, P_{26}, P_{34}, P_{35}, P_{36} \le 100000$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the largest total battle result Kim Yushin can reach.