给你一个 $n$ 行, 其中第$i$行有$i$个数的数字三角形。
你要从上往下走,每次可以走到下面一行的相邻两个位置。你希望走到最下面一行,希望经过的数字之和尽量大。
输入格式
第一行一个整数$n$。接下来$n$行,每行若干个数字。
输出格式
一个整数,表示最大的数字和。
样例输入
4
1
3 2
4 5 6
10 9 8 7
样例输出
18
数据规模
对于所有数据,$1\leq n \leq 1000$,数字大小不超过$10^5$。
给你一个 $n$ 行, 其中第$i$行有$i$个数的数字三角形。
你要从上往下走,每次可以走到下面一行的相邻两个位置。你希望走到最下面一行,希望经过的数字之和尽量大。
第一行一个整数$n$。接下来$n$行,每行若干个数字。
一个整数,表示最大的数字和。
4
1
3 2
4 5 6
10 9 8 7
18
对于所有数据,$1\leq n \leq 1000$,数字大小不超过$10^5$。