## IOI '94 P1 - The Triangle

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 16M

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

Figure 1 shows a number triangle.

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.
• The number of rows in the triangle is but .
• The numbers in the triangle, all integers, are between and .

#### Input Specification

The first line of input will contain an integer . The of the next lines will contain space-separated integers, denoting the values of the triangle.

#### Output Specification

The highest sum as required by the problem statement.

#### Sample Input

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

#### Sample Output

30