说明

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

游泳池划分成了一个 $n$×$m$ 的方格， 这里 $n$×$m$ 表示 $n$ 行 $m$ 列。 因 为游泳池里的水深浅不一，所以这$n$×$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） →（ 1， 2） →（ 1， 3） →（ 2， 3） →（ 2， 4） →（ 2， 5） →（ 3， 5） →（ 4， 5）

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

数据范围

对于 30% 的数据，$1 ≤ n， m ≤ 5$

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

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

来源

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

建议

请使用深搜和广搜分别实现