314001 - 方格取数

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
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题