1025: The Triangle
[Creator : ]
Description
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 >1 but ≤25.
- The numbers in the triangle, all integers, are between 0 and 99.
Input
The first line of input will contain an integer N. The ith of the next N lines will contain i space-separated integers, denoting the values of the triangle.
Output
The highest sum as required by the problem statement.
Sample Input Copy
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output Copy
30