Сложение треугольников
Посмотрите на треугольник слева от фигуры ниже. Он состоит из 9 (единичных) треугольников, расположенных в три ряда (N = 3). Очевидно, что единичный треугольник — это треугольник с N = 1.
Если вы посмотрите на фигуру несколько секунд, вы заметите, что можно найти 13 различных треугольников (которые мы будем называть под-треугольниками). Из этих 13 под-треугольников: девять — это единичные треугольники; три — с N = 2, и один — с N = 3. Следующая таблица показывает количество под-треугольников в конфигурациях с N < 5.
Определим значение единичного треугольника как целое число, записанное в этом треугольнике. В общем случае, значение треугольника — это сумма значений всех его единичных треугольников. Треугольник справа аналогичен, но с выделенным под-треугольником, имеющим наибольшее значение. Напишите программу, чтобы определить под-треугольник с наибольшим значением.
Входные данные
Ваша программа будет тестироваться на одном или нескольких тестовых случаях. Каждый тестовый случай задается в одной строке, состоящей из целых чисел, разделенных пробелами. Первое целое число — это количество рядов в тестовом случае, а оставшиеся целые числа — это значения единичных треугольников, заданные в порядке сверху вниз, слева направо. (Первый тестовый случай в примере ниже соответствует изображению.) Последняя строка входного файла содержит число 0 (оно не является частью тестовых случаев).
Максимальное количество рядов — 400. Абсолютное значение единичного треугольника меньше 1000.
Выходные данные
Для каждого тестового случая выведите результат в следующем формате:
k. V
где k — это номер тестового случая (начиная с 1), пробел, и V — максимальное значение под-треугольника в этом тестовом случае.