Adding up Triangles#1333
Take a look at the triangle on the left of the figure below. It consists of (unit) triangles arranged in three rows (N = 3). Needless to say, a unit triangle is a triangle with N = 1.
If you study the figure for a few seconds, you will notice that there are different triangles (which we will call sub-triangles). Of these sub-triangles: nine are unit triangles; three are with N = 2, and one is with N = 3. The following table lists the number of sub-triangles in configurations with N < 5.
Let's define the value of a unit triangle as the integer written in that triangle. In general, the value of a triangle is the sum of the values in all its unit triangles. The triangle on the right is the same as the other, but the sub-triangle with the largest value is highlighted. Write a program to determine the sub-triangle with the largest value.
Your program will be tested on one or more test cases. Each test case is given in a single line consisting of integers separated by spaces. The first integer is the number of rows in the test case, and the remaining integers are the values of the unit triangles, listed from top to bottom and left to right. (The first test case in the sample below is the same as the one in the figure.) The last line of the input file contains the number , which is not part of the test cases.
The maximum number of rows is . The absolute value of a unit triangle's value is less than .
For each test case, print the result in the following format:
k. V
where is the test case number (starting from ), followed by a space, and is the maximum value of a sub-triangle in that test case.
Example 1