三角形最大路径和

题目描述

探险队在山体裂缝中发现了一座由矿石堆成的三角形祭坛。祭坛自上而下共有 $n$ 层，第 $i$ 层摆放了 $i$ 堆矿石。队伍必须从顶点踏下，每一层只能走向正下方或右下方相邻的位置，直到抵达最底层。每堆矿石的价值已知，求一条价值总和最大的下行路线。

输入格式

第一行包含一个整数 $n$，表示祭坛的层数。

接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数，表示该层各堆矿石的价值。

输出格式

输出一个整数，表示可获得的最大价值总和。

输入输出样例 #1

输入 #1

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

输出 #1

30

数据范围

对于 $100\%$ 的数据，$1 \le n \le 500$，每堆矿石价值 $-10^4 \le v \le 10^4$。保证从顶点出发可以到达底层。EOF