Description

Given a number triangle consisting of n rows of numbers as shown in the following figure. Design an algorithm to calculate the maximum sum of numbers along a path from the top to the bottom of the triangle.

Programming Task:
For a given number triangle with n rows, programmatically compute the maximum sum of numbers along a path from the top to the bottom of the triangle.

Input Format

The first line contains the number of rows n in the number triangle, where 1 <= n <= 100. The following n lines contain the numbers in each row of the triangle. All numbers are in the range 0..99.

Output Format

Output the computed result. The first line should contain the maximum value.

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

30

代码在线