Description

给你一个由数字构成的金字塔，例如：

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

现在需要你写一个程序从最高点走到最底部，使该路径经过的数字和最大。对于每一步而言，可以向该点的左下方走，也可以向该点的右下方走。
在上面的样例中, 7 → 3 → 8 → 7 → 5 的路径经过的数字和最大

Format

Input

第一个行一个正整数 n ,表示行的数目。(1 ≤ n ≤ 1000)

后面每行为这个数字金字塔特定行包含的整数。(所有的整数 ∈ [0,100] )

Output

单独的一行,包含那个可能得到的最大的和。

Sample 1

Input

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

Output

30

Limitation

1s, 1024KiB for each test case.

Hint

Source

Vijos Original