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

Description

给出一个数字三角形，你从[1,1]开始出发，走到最后一行。每次站在一个点上时，可以向下走，或者向右下走。将经过的数字加起来，希望其和最大。

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Format

Input

第一行给出数字N

接下来N行描述这个数字三角形，所给出的数字为100以内的正整数。

N<=100

Output

如题

Samples

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

30