Figure 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 greater than 1 but less or equal 100.
The numbers in the triangle, all integers, are between 0 and 99.
First given the number of rows in triangle. Next rows describe the triangle itself.
Print the maximum sum from top to the base of triangle.