Description

Digital Triangle. As shown below is a digital triangle. Please write a program to calculate the maximum sum of numbers along a path from the top to the bottom. Only the sum needs to be output.

1. At each step, you can move down either diagonally to the left or diagonally to the right;

2. The number of rows in the triangle is less than or equal to 100;

3. The numbers in the triangle range from 0 to 99.

Input Format

Test data is input line by line via the keyboard. For example, the sample data should be input in the following format:

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

---

The first line contains a positive integer n, representing the number of rows in the digital triangle, where n ≤ 100;

The following n lines each contain i positive integers (for 1 ≤ i ≤ n), with all integers ranging from 0 to 99.

Output Format

The maximum sum of numbers.

```input1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5​ ``` ```output1 30 ``` ## Source

CodesOnline