Battlefield (Small)

After the Third World War almost all 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 across a battlefield.

General Kim Yushin commands $N$ generals. Among them $A$ carry armament 1, $B$ carry armament 2, and $C$ carry armament 3. They stand on a hill in one long row, side by side, looking at the enemy camp. General Kim Yushin was about to give the order to attack.

The enemy general also has $N$ generals. Among them $D$ carry armament 4, $E$ carry armament 5, and $F$ carry armament 6. They stand on the opposite hill in one long row and prepare to hold off the attack.

Just before giving the order, General Kim Yushin realized something. If the battle starts now, the generals meet in the formation they already stand in, so each pair fights one on one. If he changes the order of his row and puts an armament that suits the enemy armament in front of it, he gets a better battle result.

You are given the integers $P_{14}$, $P_{15}$, $P_{16}$, $P_{24}$, $P_{25}$, $P_{26}$, $P_{34}$, $P_{35}$, $P_{36}$. They describe the battle result when generals with the given armaments meet on the battlefield. For example, $P_{14}$ is the battle result when a general of General Kim Yushin carrying armament 1 meets a general of the enemy carrying armament 4. A positive integer means a result in favor of General Kim Yushin.

The total battle result is the sum of the $N$ individual battle results. You assist General Kim Yushin and want to maximize that sum by rearranging his generals. Compute this maximum value.

The first line contains the number of test cases $T$.
Each test case is given as four lines in this format.

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

Constraints

• All numbers are integers.
• $T \le 1000$
• $1 \le N \le 100$
• $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 case number starting from 1 and $y$ is the largest battle result General Kim Yushin can reach.