합병 충동

애크미 컨설팅 그룹이 당신을 새로 지은 테크노파크로 보냈다. 역동성과 시너지, 지속 가능성을 끌어올리라는 것이다. 그 말이 정확히 무슨 뜻인지는 모르겠지만 돈 버는 일에는 자신이 있고, 당신이 하려는 것도 결국 그 일이다.

테크노파크는 $3 \times n$ 격자로 배치된 시설로 이루어져 있다. 시설마다 스타트업이 하나씩 들어가 있고, 스타트업에는 각각 고유한 가치가 매겨져 있다. 이웃한 스타트업끼리 합병을 주선하면 가치가 올라가고, 그렇게 번 돈으로 라떼와 부리토를 파는 가게를 차리는 오랜 꿈을 이룰 수 있다.

독점 금지법 때문에 합병 한 건에는 스타트업 두 곳만 참여할 수 있고, 한 스타트업이 두 건 이상의 합병에 참여할 수는 없다. 또 두 스타트업은 서로 인접한 시설에 있을 때만 합병할 수 있다. 대각선으로 맞닿은 시설은 인접하지 않은 것으로 본다. 합병으로 생기는 추가 가치는 참여한 두 스타트업의 가치를 곱한 값이다. 어떤 스타트업은 아무 합병에도 넣지 않아도 되고, 그러면 그 스타트업에서는 추가 가치가 생기지 않는다.

추가 가치의 합이 가장 큰 합병 조합을 찾아라. 첫 번째 예제의 격자에서는 합병을 가장 잘 골랐을 때 추가 가치의 합이 171이 된다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 시설 격자의 너비 $n$ ($1 \le n \le 1000$)이 주어진다. 이어지는 세 줄에는 각각 정수가 $n$개씩 주어지며, 그 줄에 놓인 스타트업의 가치를 나타낸다. 가치는 모두 $1$ 이상 $100$ 이하이다.

$0$ 하나만 있는 줄이 나오면 입력이 끝난다.

각 테스트 케이스마다 한 줄에 Case i: v 형식으로 출력한다. $i$는 $1$부터 세는 테스트 케이스 번호이고, $v$는 합병으로 얻을 수 있는 추가 가치 합의 최댓값이다.