该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

玛利越过“崇山峻岭”，终于脱险，但是身上的钱已经全掉完了。正好发现 一个暗道，不仅可以快速绕过一片危险区域，还可以在里面得到很多的金币。这 个暗道是一个很深的洞，玛利从洞的顶端往下掉。洞里自上到下分布有很多金币， 最顶层有 1 个金币，第 2 层有 2 个金币……（每个金币的面值不完全相等），它 们在洞里正好排成一个等腰三角形的形状。玛利从第一个金币那里开始往下掉， 从本层到下一层，玛利只能选择拿到左下或右下的那个。比如金币分布：

  2
 1 3
2 4 1

玛利首先拿到最顶层的 2，然后他可以选择拿到下一层的 1 或 3，假设他选 择了 3，那么再下一步，他可以选择拿到 4 或 1。问题是，玛利能拿到的金币面 值总和最多是多少？

Format

Input

第一行有一个数 n，为金币三角形的层数。以下总共有 n（n<=100）行。

第 i+1 行有 i 个数，分别为金币的面值（<=30000），每个数之间用空格格开。

Output

只有一行，为玛利能拿到的最多的金币总面值。

Samples

3
2
1 3
2 4 1

9