While transporting muffins down a mountain Zeyu tripped and sent his muffins tumbling down.

Zeyu needs to get his muffins back, but can't travel up the mountain due to spinal issues from carrying CBOJ. Zeyu can see where the muffins are and needs your help to find the optimal path to maximize the number of muffins while always moving diagonally down to the left or diagonally down to the right. His parents are about to ask how many muffins he's bringing and he can't afford to be wrong!

Input Specification

The first line will contain a single positive integer \(1 \le N \le 10^3\).

The following \(N\) lines each contain a row of positive integers, with the \(i\)th line containing \(i\) integers, the number of muffins at each location. It can be assumed that the values are nonnegative and do not exceed \(10^9\).

Output Specification

Provide a single integer, the maximum number of muffins that Zeyu can get.

Subtasks

Subtask 1 [50%]

\(1 \le N \le 10\)

Subtask 2 [50%]

No additional constraints.

Sample Input:

5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 8

Sample Output

13

Sample Explanation

        1
       /
      1   1
       \  
    1   2   1    
       /
  1   3   3   1
       \
1   4   6   4   8

\(1+1+2+3+6 = 13\)

Note that it is impossible for Zeyu to get the \(8\) muffins at the bottom right because he would miss out on too many muffins on the left side.