Description

Observe the following number pyramid. Write a program to find a path from the top to any position at the bottom such that the sum of the numbers along the path is maximized. At each step, you can move to the left-down or right-down position from the current point:

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

Input Format

The first line contains $R$ ($1\leq R \leq 1000$), representing the number of rows. Each of the following lines contains the integers for that row of the pyramid.
All supplied integers are non-negative and do not exceed $100$.

Output Format

A single line containing the maximum possible sum.

Sample

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

86