题目描述

如下所示为一个数字三角形。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。 1、 每一步可向下或右斜线向下走； 2、 三角形行数小于等于100； 3、 三角形中的数字为0，1，…，99； 4、 路径必须经过第n/2行、第n/2列这个位置；

输入

第一行为N，表示有N行。 接下来的N行表示一个数字三角形。

输出

输出一行个整数，表示要求的最大总和

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

28