Description

Observe the following number pyramid. Write a program to find the path from the top to any point at the bottom that maximizes the sum of the numbers along the path.
At each step, you can move from the current point to the point diagonally below to the left or to the right.

In the example above, the path from 13 to 8 to 26 to 15 to 24 yields the maximum sum of 86.

Input Format

The first line contains R (1 ≤ R ≤ 1000), representing the number of rows.
Each subsequent line contains the integers for the corresponding row of the number pyramid.
All provided integers are non-negative and no greater than 100.

Output Format

A single line containing the maximum possible sum.

5
13
11 8
12 7  26
6  14 15 8
12 7  13 24 11

86