Трикутник

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

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

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

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

Вхідні дані

Першим числом є кількість рядків у трикутнику. Нижче по рядкам подано сам трикутник, числа у рядку відокремлені пропуском.

Вихідні дані

Вивести шукану найбільшу суму.

Приклади