题目描述

提示信息： 数字塔是由N 行数堆积而成 ，最顶层只有一个数 ，次顶层两个数， 以此类推 。相邻层之间的数用线连接 ，下一层的 每个数与它上一层左上方和右上方的数连接（左上方或右上方没有数则不需要连接） 。 编程实现： 有一个 N 行（2 ≤ N ≤ 50）的数字塔 ，小蓝想要从最顶层开始 ，沿着线一层一层向下移动 ，移动到最底层 。 小 蓝想找出一条移动路径， 使得路径上的数之和最大（包含顶层和底层的数）， 请计算出最大的和是多少。 例如： N = 5， 5 层的数字塔， 每层的数如下图所示： 从顶层数为 2 到底层数为 15 的路径上的数之和最大， 最大和为 48 。路径为： 2 → 3 → 18 → 10 → 15。

输入格式

第一行输入一个正整数 N（ 2 ≤ N ≤ 50） ，表示数字塔的层数 接下来输入 N 行， 其中第一行为一个正整数 ， 接下来每行的正整数比上一行多一个， 每行的正整数之间以一个英文逗号隔开（1 ≤ 正整数 ≤ 1000）。

输出格式

输出一个整数， 表示从数字塔最顶层移动到最底层的路径上的数之和的最大值。

5
2
3,12
18,8,3
5,10,13,2
4,15,7,6,8

48