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

题目描述

暑假快到啦，小 X 准备趁着这个暑假去学游泳。可是一开始小 X 就遇到了一个难题。

游泳池划分成了一个 $n \times m$ 的方格，这里 $n \times m$ 表示 $n$ 行 $m$ 列。因为游泳池里的水深浅不一，所以这 $n \times m$ 个方格对于小 X 的危险系数也会不一样。

小 X 目前需要从左上角的方格 $(1, 1)$ 出发，游到右下角的方格 $(n, m)$。小 X 每次只能从当前方格游到上下左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。

小 X 很担心会发生什么危险，所以希望你能帮他找一条危险系数最小的路径。一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。

注意：这条路径不能经过同一个方格两次（小 X 当然不希望去那么危险的地方再游一次）。

输入格式

输入数据第一行有两个用空格隔开的正整数 $n$ 和 $m$，表示泳池的行数和列数。

接下来共有 $n$ 行数据，每行有 $m$ 个用空格隔开的大于等于 0 的整数，表示每个方格的危险系数。

输出格式

输出仅有一行包含一个整数 $ans$，表示要求的从左上角的方格 $(1, 1)$ 出发，游到右下角的方格 $(n, m)$ 的最小的危险系数。

4 5
1 7 2 8 2
3 10 1 5 1
2 8 3 7 1
1 2 1 20 1

19

样例解释

路径：$(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (2,4) \rightarrow (2,5) \rightarrow (3,5) \rightarrow (4,5)$

危险系数之和为：$1 + 7 + 2 + 1 + 5 + 1 + 1 + 1 = 19$

数据规模与约定