##### Time limit: 0.05s

##### Memory limit: 0.5MB

##### Input: the-triangle.in

##### Output: the-triangle.out

##### Points by default: 10p

```
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 (Figure 1)
```

Figure 1 shows a number triangle.

# Task

Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

# Input data

The first line of the input file `the-triangle.in`

will contain an integer $n$, the number of rows. The next $n$ lines will contain space-separated integers, denoting the values of the triangle.

# Output data

The first line of the output file `the-triangle.out`

contains the highest sum as required by the problem statement.

# Constraints and clarifications

- $1 \lt n \le 100$
- The numbers in the triangle, all integers, are between $0$ and $99$.

# Example

`the-triangle.in`

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

`the-triangle.out`

```
30
```