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