314001 - 方格取数

有n×n的方格数（n≤8），其中的某些方格中填入正整数表示该方格中的数字，而其他的方格中则放入数字0，表示该方格中没有数。如下图所示：

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

输入的第一行为一个整数n，表示n×n的方格图，接下来每行有三个整数，前两个表示位置，第三个数为该位置上的数。一行单独的0表示输入结束。

两条路径上取得的最大和。