数字三角形 描述 下面给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和。路径上的数的和越大，路径就越优。你的任务就是找到最优路径上的数的

数字三角形

描述

下面给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和。路径上的数的和越大，路径就越优。你的任务就是找到最优路径上的数的和。1z1100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

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

1z1100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
注意：路径上的每一步只能从一个数走到它正下方的数或正下方的数的右边的那个数。1z1100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

输入的是一行是一个整数N (1 < N <= 15)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最优路径上的数的和

样例输入

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

样例输出

30

提示

样例解释：7 3 8 7 5是最优路径1z1100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
此题用递归完成。用MaxNum(r,c)表示从第r行第c列的数到底边的最大和1z1100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
考虑先走一步后问题会变成什么样。1z1100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一步有两种走法，向下，和向右下，考虑走出这一步后剩下的问题变成什么样