Number Pyramid

Problem Background

Special for beginners, ^_^

Problem Description

Consider the number pyramid above. Write a program to find a path from the top to any point at the bottom that maximizes the sum of numbers along the path. From each point you may step down-left or down-right.

In the example above, the path from $13$ to $8$ to $26$ to $15$ to $24$ yields the maximum sum $86$.

Input Format

The first line contains $R\ (1\le R\le 1000)$ — the number of rows.

Each of the following lines contains the integers of a specific row of the pyramid.

All supplied integers are non-negative and not greater than 100.

Output Format

A single line containing the maximum possible sum.

Sample Input

5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11

Sample Output

86

Constraints

$1\le R\le 1000$; all integers are non-negative and $\le 100$.

Time limit 1s, memory limit 1024KiB for each test case.