Треугольник

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

• Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.

• Число строк в треугольнике больше 1 и меньше или равно 100.

• Треугольник составлен из целых чисел от 0 до 99.

Входные данные

Первым числом является количество строк в треугольнике. Ниже по строкам представлен сам треугольник, числа в строке разделены пробелом.

Выходные данные

Вывести наибольшую сумму на пути от вершины до основания треугольника.

Примеры