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

【题目描述】3取方格数(getnum3.cpp/c/pas) Vijos1143

张琪曼和李旭琳两人正准备捡魔法石，却见楚继光从后面飞奔而来，大喊道：“不好意思，不好意思，我来晚了，捡魔法石这样的好事一定要带上我一起啊。”

所以现在的问题变为，设有N×N的方格数，其中的某些方格中填入正整数表示方格中魔法石的数量，而其他的方格中放入数字0代表没有魔法石。

楚继光三人从图的左上角的A点出发，可以向下走，也可以向右走，直到到达右下角的B点，在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。从A点到B点一人走一次，试找出3条这样的路径，使得取得的数之和为最大。

【输入格式】

　  第一行为一个整数N (4≤N≤20)，接下来是一个N×N的矩阵，矩阵中每个元素不超过10000，不小于0。

【输出格式】

一行，表示最大的总和。

【输入样例】

4

1 2 3 4

2 1 3 4

1 2 3 4

1 3 2 4

【输出样例】

39