The Triangle

        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