探索数字迷塔
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
问题描述
设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如上图所示：
从根结点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 1186