Description

A triangle composed of positive integer digits, as shown below:

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

There are many different paths from the top to the bottom of the triangle.

For each path, the sum of the numbers along the path can be calculated, and the path with the largest sum is called the optimal path. Your task is to find the sum of the numbers on this optimal path.

Note: At each step of the path, you can only move to the number directly below (vertically down) or to the number below and to the right (diagonally down-right) of the current number.

Input Format

The first line contains the height of the triangle, h, where 100 ≥ h ≥ 1, which also represents the number of numbers on the bottom row.
Starting from the second line, each subsequent line represents the numbers in the corresponding row of the triangle, separated by spaces.

Output Format

The numerical value of the sum of the optimal path.

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

30