Type: Default

1000ms

128MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如上图所示：

从根结点13出发向左、向右的路径长度可以是：

13－11－7－14－7，其和为52

13－11－12－14－13，其和为63若要求从根结点开始，请找出一条路径，使路径之和最大。

输入格式

第一行：一个整数n（1<=n<=1000),表示数字迷塔的高度

接下来用n行数字表示数字迷塔，其中第i行有i个正整数，且所有的正整数均不大于100

输出可能得到的最大和。

5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11