Maximum Path Sum in a Triangle

Given a number triangle as shown below, start from the top. At each node, you can choose to move to the node directly below-left or directly below-right. Continue moving to the bottom. The task is to find a path that maximizes the sum of the numbers along the path.

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

Input Format

The first line contains an integer n, representing the number of rows in the number triangle.

The next n lines each contain several integers, where the i^th line represents the integers contained in the i^th row of the number triangle.

Output Format

Output a single integer, representing the maximum possible path sum.

Constraints

1 ≤ n ≤ 500

-10000 ≤ Triangle integers ≤ 10000

Sample Input

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

Sample Output

30