The Triangle#3189
A triangle of numbers is shown in the figure. Write a program that calculates the greatest sum of numbers along a path that begins at the top of the triangle and ends at its 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 greater than and less than or equal to .
The triangle is formed by integers from to .
The first line contains the number of rows in the triangle.
The following lines describe the triangle itself, with numbers in each line separated by spaces.
Print the greatest sum on a path from the top to the base of the triangle.
Example 1