Description

Look at the number pyramid below.

Write a program to find a path from the top to any position on the bottom that yields the maximum possible sum of the numbers along the path. At each step, you may move to the left-down or right-down adjacent position.

In the sample above, the path $7 \to 3 \to 8 \to 7 \to 5$ produces the maximum sum.

Input Format

The first line contains a single integer $r$, the number of rows.

Each of the next $r$ lines describes one row of the number triangle: for each $i$ from $1$ to $r$, the $i$-th line contains $i$ integers.

Output Format

Output a single line containing the maximum possible sum.

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

30

Hint

Constraints
For $100\%$ of the testdata, $1 \le r \le 1000$, and all input integers are in the range $[0, 100]$.

Problem translation from NOCOW.
IOI 1994 Day 1 T1 / USACO Training Section 1.5.

Translated by ChatGPT 5