现有甲、乙两人分别从地图的左上角出发，他们可以向下行走，也可以向右行走，直到到达右下角。在走过的路上，他们可以取走方格中的魔法石，取走后的方格中将变为数字0。
【编程任务】试找出两条这样的路径，使得甲和乙两人取得的魔法石数量之和最大。
1950: 取魔法石
时间限制: 1 Sec 内存限制: 128 MB提交: 6 解决: 6
[提交][状态][讨论版]
题目描述
有一个N行N列的方格地图，在地图的某些方格中有若干数量的魔法石。如下图所示，方格中的数字表示该方格中的魔法石数量，数字为0则表示该方格中没有魔法石。
现有甲、乙两人分别从地图的左上角出发，他们可以向下行走，也可以向右行走，直到到达右下角。在走过的路上，他们可以取走方格中的魔法石，取走后的方格中将变为数字0。
【编程任务】试找出两条这样的路径，使得甲和乙两人取得的魔法石数量之和最大。
现有甲、乙两人分别从地图的左上角出发，他们可以向下行走，也可以向右行走，直到到达右下角。在走过的路上，他们可以取走方格中的魔法石，取走后的方格中将变为数字0。
【编程任务】试找出两条这样的路径，使得甲和乙两人取得的魔法石数量之和最大。
输入
输入第一行为一个整数N（N≤10），表示N行N列的方格地图。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的魔法石数量。
一行0 0 0表示输入结束。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的魔法石数量。
一行0 0 0表示输入结束。
输出
输出包含一个整数，表示两条路径上取得的最大的和。
样例输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0样例输出
67