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