时间限制：1秒　　内存限制：256M

---

【题目描述】

　　设有 \(N×N\) 的方格图，我们将其中的某些方格填入正整数，而其他的方格中放入 0 。某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。在走过的路上，他取走了方格中的数（取走后方格中数字变为 0）。此人从左上角到右下角共走 3 次，试找出 3 条路径，使得取得的数总和最大。

【输入格式】

　　第一行: \(N\)
　　接下来一个 \(N×N\) 的矩阵，矩阵中每个元素不超过 80，不小于 0。

【输出格式】

　　一行，表示最大的总和。

【输入输出样例】

　Input

4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4

　Output

39

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤20\)。

【来源】

　　Mr.he