Задача Gold
Знаходячись на вершины гори потрібно спуститься вниз. Від вершини до основи збудовано оригинальні сходи: з кожної сходинки можна зробити крок вниз
на наступний рівень тільки по діагоналі вправо чи по діагоналі вліво. Число рівній на горі >1 и <=100. На кожній сходинці знаходится ціле число золотих монет (від 0 до 99). Напишіть програму, яка обчислить найбільшу суму монет, яку можна зібрати на шляху від вершини до основи. Ось приклад такой гори:
5
5 4
2 1 8
1 7 3 4
4 5 6 1 1
Технічні умови. Програма читає з клавіатури кількість рівнів, а далі - кількість монет на кожній сходинці кожного рівня. Всі числа записано в один рядок через пропуск. Програма виводить на екран єдине число - максимально можливу кількість монет на маршруті
Приклад
Введення
5 5 4 2 1 8 1 7 3 4 4 5 6 1 1
Виведення
25