Source : 第六届全国青少年信息学(计算机)奥林匹克分区联赛[2000年12月2日]
Description
设有N*N的方格图,我们将其中的某些方格填入正整数, 而其他的方格中放入0。 某人从图得左上角出发,可以向下走,也可以向右走,直到到达右下角。 在走过的路上,他取走了方格中的数。(取走后方格中数字变为0) 此人从左上角到右下角共走3次,试找出3条路径,使得取得的数总和最大。
Input
第一行:N (4< =N< =20) 接下来一个N*N的矩阵,矩阵中每个元素不超过80,不小于0
Output
一行,表示最大的总和。
Sample Input
3
1 1 10
1 3 5
2 2 6
2 3 4
3 1 8
3 2 2
0 0 0
Sample Output
30