전장 (Large)

문제

제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_{ij}$ 는 김유신 장군의 $i$ 번 무장 장수가 적 장군의 $j$ 번 무장 장수를 만났을 때의 전투 결과다. 양수는 김유신 장군에게 유리한 결과를 뜻한다.

전체 전투 결과는 각 1대 1 전투 결과의 합이다. 줄의 순서를 바꿔 얻을 수 있는 전체 전투 결과의 최댓값을 구하시오.

입력

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

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

제한

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

출력

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