전장 (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$는 김유신 장군이 얻을 수 있는 전체 전투 결과의 최댓값이다.