전장 (Small)

문제

제3차 세계대전이 끝난 뒤 현대 기술은 거의 사라지고 살아남은 사람도 얼마 되지 않았다. 인류는 천천히 복구하며 새 역사를 써 나갔다. 수천 년이 지난 새로운 중세, 김유신 장군은 전장에서 적 장군과 대치했다.

김유신 장군 휘하에는 장수 $N$ 명이 있다. 그중 $A$ 명은 1번 무장, $B$ 명은 2번 무장, $C$ 명은 3번 무장을 갖췄다. 장수들은 언덕 위에 옆으로 길게 한 줄로 서서 상대 진지를 바라보고 있다. 김유신 장군은 막 공격 명령을 내리려는 참이었다.

적 장군에게도 장수 $N$ 명이 있다. 그중 $D$ 명은 4번 무장, $E$ 명은 5번 무장, $F$ 명은 6번 무장을 갖췄다. 이들도 반대편 언덕에 올라 옆으로 길게 한 줄로 서서 공격을 막을 준비를 하고 있다.

공격 명령을 내리려던 그때 김유신 장군은 한 가지를 깨달았다. 지금 싸우면 양쪽 장수는 줄을 선 대형 그대로 짝을 지어 1:1로 맞붙는다. 줄을 선 순서를 바꿔 상대 무장에 잘 맞는 무장을 배치하면 더 좋은 전투 결과를 얻을 수 있다.

입력으로 정수 $P_{14}$ , $P_{15}$ , $P_{16}$ , $P_{24}$ , $P_{25}$ , $P_{26}$ , $P_{34}$ , $P_{35}$ , $P_{36}$ 을 받는다. 이 수는 각 무장의 장수가 전장에서 만났을 때 전투 결과가 어떻게 되는지를 나타낸다. 예를 들어 $P_{14}$ 는 김유신 장군의 1번 무장 장수가 적 장군의 4번 무장 장수를 만났을 때의 전투 결과다. 양의 정수는 김유신 장군에게 유리한 결과를 뜻한다.

전체 전투 결과는 1:1 전투 결과 $N$ 개의 합이다. 김유신 장군의 보조역인 당신은 아군 장수를 재배열해 이 합을 최대로 만들려고 한다. 이 최댓값을 계산하시오.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다.
각 테스트 케이스는 다음과 같이 네 줄로 주어진다.

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

제한

모든 수는 정수다.
$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$

출력

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 케이스 번호이고, $y$ 는 김유신 장군이 얻을 수 있는 최대 전투 결과다.