Cow Pinball

The cows are playing a game called pachinko. You drop a ball in at the top, and as it falls it strikes nails, veering a little to the left or right, until it comes out at the bottom.

This pachinko machine is special. The ball always strikes the single top nail of the $R$ rows of nails ($1 \le R \le 25$), and then hits either the left or right nail just below it. From there it again falls to the left or right nail just below, and this repeats all the way down to the last row. The ball never veers too far — no more than half a nail — from the nail it just struck.

Scoring is unusual too: you earn points $X_{ij}$ ($0 \le X_{ij} \le 3000$) for every nail you strike on the way down. The cows want to maximize their score. What is the highest score they can achieve?

Here is an example triangle and a good route; the nails marked with * form the path.

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

In the example above, the route $7 \to 3 \to 8 \to 7 \to 5$ gives the highest sum, $30$. Going from $7$ to $8$ and then to $8$ again is impossible: the $8$ in the third row is too far away.

• Line 1: a single integer $R$.
• Lines 2 to $R+1$: line $i+1$ contains the $i$ space-separated scores of the $i$-th row of the machine: $X_{i1}, X_{i2}, \dots, X_{ii}$.

• Line 1: a single integer, the maximum achievable score.