삼각형의 값

큰 삼각형은 $N$개의 줄로 이루어져 있고, 위에서 $i$번째 줄에는 $2i-1$개의 단위 삼각형이 있다. 따라서 $N$줄짜리 삼각형은 모두 $N^2$개의 단위 삼각형으로 나뉜다. 각 줄에서 단위 삼각형은 위를 향한 삼각형(▲)과 아래를 향한 삼각형(▽)이 번갈아 나타나며, 양 끝은 항상 위를 향한 삼각형이다.

부분 삼각형이란 이 단위 삼각형들을 모아서 만들 수 있는, 위 또는 아래를 향한 정삼각형을 말한다. 예를 들어 $N=3$인 삼각형(단위 삼각형 9개) 안에는 서로 다른 부분 삼각형이 모두 13개 있다. (한 변이 단위 삼각형 1개인 것 9개, 2개인 것 3개, 3개인 것 1개)

일반적으로 $N$줄짜리 삼각형 안에 들어 있는 부분 삼각형의 개수는 $N=1$이면 1개, $N=2$이면 5개, $N=3$이면 13개, $N=4$이면 27개이다.

각 단위 삼각형에는 정수 값이 하나씩 적혀 있다. 부분 삼각형의 값은 그 부분 삼각형에 포함된 모든 단위 삼각형에 적힌 값의 합이다.

삼각형에 적힌 값들이 주어졌을 때, 값이 가장 큰 부분 삼각형의 값을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 주어진다. 줄의 맨 앞 정수는 줄의 수 $N$이고, 그 뒤로 단위 삼각형에 적힌 값이 위에서 아래로, 그리고 각 줄에서는 왼쪽에서 오른쪽 순서로 $N^2$개 주어진다.

입력의 마지막 줄에는 $0$ 하나만 주어지며, 이는 입력의 끝을 나타낸다.

줄의 수 $N$은 400을 넘지 않으며, 각 단위 삼각형에 적힌 값의 절댓값은 1000을 넘지 않는다.

각 테스트 케이스마다 한 줄에 번호. 값 형식으로 출력한다. 번호는 1부터 시작하는 테스트 케이스 번호이고, 값은 그 테스트 케이스에서 값이 가장 큰 부분 삼각형의 값이다. (번호와 값 사이에는 마침표와 공백이 하나씩 들어간다.)