Digits are printed in a right-angled triangle format - first line contains one digit second line contains two digits etc upto n lines. Each digit ranges from 0-9. 
The player can traverse along the triangle in a path according to the rules given below:

1. He moves one step down every move till the last level
2. He can either move to the digit directly below the current position or  to the one to the right of the digit below in the next row and not elsewhere..
Eg.
if the given sequence is 
1
2 3
6 7 8 
From 2 he can move to either 6 or 7
From 3 he can move to either 7 or 8

3.The number he visits is added to the sum which is initially the element in the first row.

Write a program to simulate such a motion and find a suitable path for the given input such that the sum is the maximum among all the paths traversed.


Input

The first line contains an integer n - number of lines of digits in the triangle.
Followed by n lines of triangle code ( i th line must contain only i digits)

Output
The maximum sum for that output.(path not required)

Sample Input:
3
1
2 1
1 3 5

Sample Output:
7