Задачі
Трикутник
Трикутник
На рисунку зображено трикутник з чисел. Напишіть програму, яка обчислює найбільшу суму чисел, розміщених на шляху, який починається у верхній точці трикутника і завершуєься на основі трикутника.
- Кожен крок на шляху може здійснюватись униз по діагоналі ліворуч або униз по діагоналі праворуч.
- Число рядків у трикутнику більше 1 і менше або рівне 100.
- Трикутник складено з цілих чисел від 0 до 99.
Вхідні дані
Першим числом є кількість рядків у трикутнику. Нижче по рядкам подано сам трикутник, числа у рядку відокремлені пропуском.
Вихідні дані
Вивести шукану найбільшу суму.
Вхідні дані #1
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Вихідні дані #1
30