Triangle

You are given a triangle of numbers in the format of the following diagram:

Imagine starting from the top vertex of the triangle and moving downwards towards the base, summing numbers. At each step, you can either move diagonally down and left or diagonally down and right. For example, you can follow the path ~7~, ~3~, ~1~, ~4~, ~2~, and by summing these numbers, you get a total of ~17~.

Problem:

Develop a program in one of the IOI languages which, after reading the numbers that make up the triangle, calculates the maximum sum of the numbers encountered starting from the top vertex of the triangle and ending at some point on the bottom base.

Input Files:

The input files named triangle.in are text files with the following structure: The first line contains an integer ~N\;(1 \le N \le 1000)~, representing the number of lines of the triangle. The next ~N~ lines contain the integer numbers of each line of the triangle, from left to right, separated in pairs by a single space. These numbers will be between ~0~ and ~99~.

Output Files:

The output files named triangle.out are text files with the following structure: They have one line with exactly one number, the maximum sum that can be achieved.

Example of Input - Output Files:

STDIN (triangle.in)

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

STDOUT (triangle.out)

30

Explanation of the example:

The input corresponds to the triangle in the diagram of the previous page. The maximum sum is ~30~ and arises from the path ~7~, ~3~, ~8~, ~7~, ~5~.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 16 MB.