由于校赛,OJ将于本周五(5.17)到周日停止服务

Problem 1791. -- 数塔问题

1791: 数塔问题

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 419  Accepted: 306
[Submit][Status][Web Board]

Description

设有一个三角形树塔,第一层1个整数,第二层2个整数,第三层3个整数,...。从第一层出发可以向下走或右下走。若要求从第一层开始,到最下一层,请找出一条路径,使路径之和最大,只要输出路径的和。

例如下图所示的树塔,从第一次出发,路径整合最大的一条路径为13,8,26,15,13,路径的和为86。

        13

        11      8

        12      7    26

          6    14    15      8

        12      7    13    24    11

Input

包含多组测试数据。每组测试数据的第一行为一个整数n(n<10),表示数塔的层数,从第2行至n+1行,每行有若干个数据,表示数塔中的数值。

Output

 每组测试数据输出占一行,输出路径和最大的路径值。

Sample Input

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

Sample Output

86

Source

[Submit][Status][Web Board]