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

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

В примере путь через 7, 3, 8, 7, 5 даёт максимальную сумму 30.

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

Первая строка содержит число рядов $R$ ($1 \le R \le 1000$). Каждая следующая строка содержит целые числа соответствующего ряда треугольника. Все числа неотрицательны и не больше 100.

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

Одна строка с максимальной суммой при указанном обходе.

Примеры

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

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

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

30