Value of a Triangle

A large triangle has $N$ rows; the $i$-th row from the top contains $2i-1$ unit triangles, so an $N$-row triangle is divided into $N^2$ unit triangles in total. Within each row the unit triangles alternate between upward-pointing (▲) and downward-pointing (▽) triangles, and both ends of every row are always upward-pointing.

A sub-triangle is any upward- or downward-pointing equilateral triangle that can be assembled from these unit triangles. For example, an $N=3$ triangle (9 unit triangles) contains 13 distinct sub-triangles in total (9 with a side of 1 unit triangle, 3 with a side of 2, and 1 with a side of 3).

In general the number of sub-triangles inside an $N$-row triangle is 1 for $N=1$, 5 for $N=2$, 13 for $N=3$, and 27 for $N=4$.

Each unit triangle has one integer written in it. The value of a sub-triangle is the sum of the values written in all unit triangles it contains.

Given the values written in the triangle, write a program that finds the largest possible value of a sub-triangle.

The input consists of several test cases, each given on one line. The first integer on the line is the number of rows $N$, followed by the $N^2$ values written in the unit triangles, listed from top to bottom and, within each row, from left to right.

The last line of the input contains a single $0$, which marks the end of the input.

The number of rows $N$ does not exceed 400, and the absolute value written in each unit triangle does not exceed 1000.

For each test case, print one line in the format index. value, where index is the 1-based test-case number and value is the largest sub-triangle value for that test case. (A period and a single space separate index and value.)