Integer Triangle

        7      3   8    8   1   0  2   7   4   44   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.

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.

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