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. Each step can move down along the left diagonal or the right diagonal;

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, indicating the number of rows in the digital triangle, where n ≤ 100;

The following n lines each contain i positive integers (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