Integer Triangle

Interview

Time limit2sMemory limit128 MB

Summary

Given a triangle of up to 500 rows, compute the maximum sum path from top to bottom moving diagonally at each step.

Level: Easy3 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

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

The figure above is an integer triangle of size 5.

Start at the number 7 on the top row and move down one row at a time. At each step, you may choose only one of the two numbers diagonally down-left or diagonally down-right from the current number. Write a program that finds the maximum possible sum of the numbers selected on a path from the top row to the bottom row.

The triangle size is between 1 and 500 inclusive. Each number in the triangle is an integer between 0 and 9999 inclusive.

Input

The first line contains the triangle size n (1 <= n <= 500). The next n lines contain the integer triangle from top to bottom. The i-th of these lines contains i integers separated by spaces.

Output

Print the maximum possible sum of the selected numbers on any path from the top row to the bottom row.

Examples1

Example 1
Input
```
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
```
Expected output
```
30
```