U538485 迷你才不是盗版游戏

题目描述

Spring 终于放学了！Spring 的学校只在每周六放一天的假期，Spring 现在赶着回家玩迷你世界。

班里的每个人都有一个对迷你世界的讨厌值 $a_{i,j}$ ，而作为一个资深的迷你玩家，Spring 打心底讨厌那些玩 MC 的人。所以他在从自己的座位走到教室前门的时候会尽可能地避开玩 MC 的同学。

现在 Spring 急着回家玩迷你世界，但 Spring 的 naoz 实在是太 low 了，所以请你帮 Spring 算一下出门的最优路线（尽可能减少路上遇到的人的对迷你世界的讨厌值的总和）。

由于 Spring 急着回家玩迷你世界，所以你只有 $1s$ 的时间。

输入格式

共 $n+1$ 行。

第一行一个整数 $n$，表示教室有多少行和多少列。

接下来 $n$ 行，每行 $n$ 个数字，每个数字 $a_{i,j}$ 表示从这里经过时会累加的讨厌值，Spring只能往上，下，左，右走，不能斜向走。

保证有Spring的座位 $a_{n,n}=0$ 。

输出格式

一个整数 $k$ ，表示 Spring 去班级前门 $(1,1)$ 路上遇到的人的对迷你世界的讨厌值的总和的最小值。

输入输出样例 #1

输入 #1

3
3 1 2
1 1 4
5 1 0

输出 #1

6

输入输出样例 #2

输入 #2

3
4 8 2
1 7 0
1 2 3

输出 #2

11

说明/提示

【数据范围】

对于 $100\%$ 的数据，保证 $2 \le n \le 50$ 且 $k$ 在 $int$ 范围内。