跳房子游戏

题目描述

第一名是我的！它总是我的！ 小赢家跃入灰白屋。 第三名，第三名，还是第三名。 可恶！可恶！可恶！ 那抹橙跳出粉笔格，跳出了灰白屋。 她又要去哪儿了？小赢家嘟囔着，我还能见到她吗？

玛蒂尔达一个人在玩跳房子游戏，才不是因为十四行诗去找维尔汀了呢...明明，我一个人也能玩！

跳房子游戏在一个 $n \times n$ 的网格图进行，玛蒂尔达最开始位于 $(1,1)$，游戏的终点在 $(n,n)$，每个格子都有一个数字 $a_{ij}$，玛蒂尔达可以向上下左右四个格子进行移动，每次移动都会累加上格子上的数字。玛蒂尔达想知道，走到终点时，自己累加的数字之和最小是多少？

输入格式

第一行为一个整数 $n$，表示矩阵大小。 接下来是一个 $n \times n$ 的矩阵。

保证 $a_{11} = 0$。

数据范围

$1 \le n \le 500$ $1 \le a_{ij} \le 10^5$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

13