测试数据来自 system/1839

作业已超过截止时间，您无法递交本题目。

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

---

【题目描述】

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

【输入格式】

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

【输出格式】

　　一行，表示最大的总和。

【输入输出样例1】

　Input

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

　Output

39

【数据限制】

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

【来源】

　　Mr.he