2125: 宝典2第十一章方格取数

【题目描述】方格取数(GetNum.cpp/c/pas) NOIP 2000

张琪曼：“哇，想不到墨家宝库中还有这么多魔法石。”

李旭琳：“但是看上去好像要按照规则取魔法石才行，否则会发生危险的。”

简而言之就是有n×n的方格数（n≤8），其中的某些方格中填入正整数表示该方格中的魔法石数量，而其他的方格中则放入数字0，表示该方格中没有魔法石。如图所示：

现从左上角出发，可以向下行走也可以向右走，直到到达右下角，在走过的路上，他可以取走方格中的数，取走的方格数将变为0，张琪曼和李旭琳各走一次，试找出两条这样的路径，使得取得的数之和最大。

【输入格式】

　　输入的第一行为一个整数n，表示n×n的方格图，接下来每行有三个整数，前两个表示位置，第三个数为该位置上的数。一行单独的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