收集样本问题

Description:

机器人Rob在一个有n*n个方格的方形区域F 中收集样本。（i,j）方格中样本的价值为v(i,j)，如下图所示。

Rob从方形区域F的左上角A点出发，向下或向右行走，直到右下角的B点，在走过的路上，收集方格中的样本。Rob从A点到B 点共走2次，试找出Rob的2条行走路径，使其取得的样本总价值最大。

给定方形区域F中的样本分布，编程计算Rob的2条行走路径，使其取得的样本总价值最大。

Input:

输入第1行有1个正整数n，表示方形区域F有n*n个方格。接下来每行有3个整数，前2个表示方格位置，第3个数为该位置样本价值。最后一行是3个0。

Output:

输出计算的最大样本总价值。

Sample Input:

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

Sample Output:

67

Note:

undefined

本题由旧版NOJ导入，来源：算法设计与实验题解