测试数据来自 system/3089

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

---

【题目描述】

　　小Y到一个 \(N×N\) 的药草田里采药，她从左上角的格子田（第一行，第一列）出发，要到达右下角（第 \(N\) 行，第 \(N\) 列）的格子田，每次她可以向右或向下走到相邻的格子去，而且出于对美的要求，她走过的路径是关于 左下-右上 对角线对称的。由于地势不同，在每个格子田采药都会有一个疲劳度 \(T_ij\)，小Y想知道怎么走才能让他采药的疲劳度最小。

【输入格式】

　　第一行一个整数N，接下来 \(N\) 行，每行 \(N\) 个非零数字（1,2,3...9中一个），表示格子田的疲劳度。

【输出格式】

　　 输出一个整数表示答案。

【输入输出样例1】

　Input

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

　Output

21

【样例1解释】

　　一条代价最小的对称路径如下：

【输入输出样例2】

　Input

10
2 1 3 2 5 1 6 2 2 3
4 2 1 5 2 1 2 1 4 2
3 1 1 2 5 3 1 7 1 2
6 2 4 1 5 2 1 8 2 1
2 2 2 5 1 7 2 1 1 7
1 7 2 2 1 1 3 5 2 1
7 2 9 3 6 1 9 2 1 7
1 2 5 2 1 6 2 8 1 1
3 3 3 3 4 5 5 1 2 4
4 2 1 5 1 2 1 6 2 1

　Output

35

【数据限制】

　　对于 \(10\%\) 的数据，\(1≤N≤5\)。
　　对于另外 \(20\%\) 的数据，\(1≤N≤40\)。
　　对于 \(100\%\) 的数据，\(1≤N≤100\)。

【来源】

　　Mr.he