描述

假定你已经通过了这个题目的小数据规模版本，这里有大数据版本可供挑战。

数字塔是由 $N$ 行数堆积而成，最顶层只有一个数，次顶层两个数，以此类推。相邻层之间的数用线连接，下一层的每个数与它上一层左上方和右上方的数连接（左上方或右上方没有数则不需要连接）。

编程实现：有一个 $N$ 行( $0≤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