暑假快到啦，小 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$ 的整数， 表示每个方格的危险系数

【数据范围】

对于 $30\%$ 的数据， $1\le n,m\le 5$

对于另外 $40\%$ 的数据， $1\le n,m\le 20$ ， 每个方格的危险系数 = $0$ 或 $1$

对于 $100\%$ 的数据， $1\le n,m\le 30$， $0\le$ 每个方格的危险系数 $\le 100000$

【样例解释】

路径： $(1,1)$ → $(1,2)$ → $(1,3)$ → $(2,3)$ → $(2,4)$ → $(2,5)$ → $(3,5)$ → $(4,5)$ ， 危险系数之和为 $1+7+2+1+5+1+1+1=19$ 。

【来源】

常州市2016“信息与未来”夏令营选拔赛