Ограничение памяти: 64 М байт

Входной файл: Input.txt

Выходной файл: Output.txt

Ограничение времени: 1 секунда

Ограничение памяти: 64 М байт

Дан треугольник из чисел. Напишите программу, которая находит наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника. Каждый шаг может осуществляться вниз по диагонали влево или вниз по диагонали вправо.

Вход

Входной файл содержит несколько строк. В первой строке записано целое число N (1 ≤ N ≤ 100) - количество строк треугольника. В следующих N строках файла содержатся строки треугольника, состоящие соответственно из 1, 2, ..., N чисел. Все числа целые и не превосходят по модулю 1,000,000.

Выход

В выходной файл следует вывести найденную максимальную сумму.

Пример входа и выхода

Задача 2. «Квадраты»

Входной файл: Input.txt

Выходной файл: Output.txt

Ограничение времени: 1 секунда

Ограничение памяти: 64 М байт

Васе часто приходится использовать тетради «в клетку». Вася положительно относится к клетчатой бумаге, но только если такая бумага имеет строго квадратную форму. В противном случае, прежде чем использовать бумагу, он разрезает её на квадратные куски. Пусть, например, лист имеет размер 6 на 7 квадратов, тогда Вася может разделить его на квадратные куски, выполнив 4 разреза:

Но Васе приходится тратить слишком много времени, разрабатывая оптимальный план разрезания бумаги. Помогите Васе – напишите программу, находящую наименьшее количество разрезов, позволяющих разделить лист бумаги заданного размера на квадратные куски.

Вход

Во входном файле записаны два целых числа N и M – размеры листа (1 ≤ N, M ≤ 100).

Выход

Запишите в выходной файл минимальное количество разрезов, позволяющих разделить лист на квадратные куски.

Пример входа и выхода

Задача 3. "Роман"