By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

\(\begin{gather*} \mathbf{3} \\ \mathbf{7} \qquad 4 \\ 2 \qquad \mathbf{4} \qquad 6 \\ 8\qquad 5 \qquad \mathbf{9} \qquad 3 \\ \end{gather*}\)

That is, 3 + 7 + 4 + 9 = 23.

Write a program that finds such longest path for every triangle.

Grading

Your program will go through two tests. The first one is significantly smaller than the second one. They award respectively 2 and 8 points.

Output Specification

For every input, there is one line per row of the triangle.

Sample Input

3
7 4
2 4 6
8 5 9 3

Sample Output

23

Source: Project Euler