给你一个 $n$ 行， 其中第$i$行有$i$个数的数字三角形。

你要从上往下走，每次可以走到下面一行的相邻两个位置。你希望走到最下面一行，希望经过的数字之和尽量大。

输入格式

第一行一个整数$n$。接下来$n$行，每行若干个数字。

输出格式

一个整数，表示最大的数字和。

样例输入

4
1
3 2
4 5 6
10 9 8 7

样例输出

18

数据规模

对于所有数据，$1\leq n \leq 1000$，数字大小不超过$10^5$。