Problem A
Crawling Q-Bert
Q-Bert has lost his jumping skills and just wants to get off the pyramid. All he can do is crawl from one platform to either of the two neighbouring platforms one level below.
Alas, the walls of the pyramid are infested by venomous spiders, against which Q-Bert has no defence! The spiders do different amounts of damage. The goal for Q-Bert is to reach the floor with as little damage as possible. He starts at the topmost platform.
![\includegraphics[width=6cm]{img/sample-1.png}](/problems/itu.qbert/file/statement/en/img-0001.png)
Notation
Let us fix some notation and terminology.
A pyramid of height $h$ has exactly $\frac12 h(h+1)$ platforms. We say that the topmost platform is at level $1$. The bottommost $h$ platforms are at level $h$. The area below those platforms is called the floor. In general, there are exactly $j$ platforms on level $j$. Each platform has two walls below it, so the number of walls at level $j$ is $2j$.
We enumerate the plaforms starting in $0$, so the topmost platform is platform $0$, and its two neighbours at level $2$ are platforms $1$ and $2$. In general, from platform $i$ on level $j$ ($1\leq j < h$), Q-Bert can reach platform $i+j$ (by crawling to the left) and platform $i+j+1$ (by crawling to the right). From level $h$, he will always reach the floor, no matter which direction he crawls in.
![\includegraphics[width=8cm]{img/sample-3.png}](/problems/itu.qbert/file/statement/en/img-0002.png)
Input
On the first line, an integer $h$, the height of the pyramid. Then follow $h$ lines. The $j$th of these lines ($1\leq j\leq h$) consists of $2j$ positive integers separated by space, giving the damage inflicted by the spiders on the walls of the $j$th level of the pyramid, from left to right. Damage is at least $0$ and at most $1000$
Output
A single integer, the minimum amount of damage Q-Bert takes on any path from the top to the floor of the pyramid.
Test groups
The problem instances are partitioned into various test groups, which include additional constraints on problem sizes and spider damages. (Test group 1 promises $h\leq 15$, test group 2 promises $h\leq 50$, and the spiders in test group 3 do only $0$ or $1$ damage.)
A correct solution to the problem gets 4 points.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 2 4 3 2 5 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 1 2 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 1 2 8 6 3 4 0 5 1 2 3 2 |
6 |
| Sample Input 4 | Sample Output 4 |
|---|---|
3 0 0 0 0 0 0 1 1 1 1 1 0 |
0 |
| Sample Input 5 | Sample Output 5 |
|---|---|
3 0 0 0 0 0 0 0 1 1 1 1 1 |
0 |
| Sample Input 6 | Sample Output 6 |
|---|---|
2 1 3 1 1 0 1 |
2 |
| Sample Input 7 | Sample Output 7 |
|---|---|
2 3 1 1 0 1 1 |
2 |
