$\text{Maximum Path}$

Given is a triangle of numbers. A path through the triangle is a sequence of adjacent numbers, one from each row, starting from the top. For example, $1\to 3\to 3\to 4\to 1\to 0$ is a path in the following triangle of numbers:

$$\begin{array}{c}\mathbf{\text{1}}\\ \mathbf{\text{3}}5\\ 6\mathbf{\text{3}}2\\ 31\mathbf{\text{4}}9\\ 98\mathbf{\text{1}}57\\ 46\mathbf{\text{0}}282\end{array}$$

Your task is to find the maximum path cost, where the path cost is defined as the sum of the numbers in the path. Thus, the given example has a maximum path cost of $1+5+2+9+7+8=32$, as shown below:

$$\begin{array}{c}\mathbf{\text{1}}\\ 3\mathbf{\text{5}}\\ 63\mathbf{\text{2}}\\ 314\mathbf{\text{9}}\\ 9815\mathbf{\text{7}}\\ 4602\mathbf{\text{8}}2\end{array}$$

Write a program that reads a triangle of numbers and outputs the maximum path cost. The first line of the input contains the number of rows. Each subsequent line represents a row of the triangle, starting with the top row. Within each row, the numbers are separated by a space. The triangle has at most 1000 rows. All numbers are positive integers between 0 and 100.

$\text{Example}$

Input:

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

Output:

32