Number Tower

Problem Background

Special for beginners, ^_^

Problem Description

Consider a triangular number tower with the apex as the root node, each node holding an integer value. Starting from the apex, you may go left or right, as shown in the figure:

Starting from the root node, find a path that maximizes the sum along the path; you only need to output the maximum path sum.

Input Format

The first line is $n\;(n < 10)$, the number of layers of the tower.

From the 2nd line to the $(n+1)$-th line, each line contains several values, the numbers in the tower.

Output Format

Output the maximum path sum.

Sample Input

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

Sample Output

86

Constraints

1s, 1024KiB for each test case.