题目内容

在 $PCB$ 印刷电路板设计中，器件之间的连线需要避免线路的阻抗值增大、而且赛件之间还有别的器件和别的干扰源，在布线时我们希望受到的干扰尽量小。

现将电路板简化成一个 $M×N$ 的矩阵，每个位置(单元格)的值表示其源干扰度。

如果单元格的值为 $0$ ，表示此位置没有干扰源;如果单元格的值为非 $0$ ，则表示此位置是干扰源，其值为源干扰度。连线经过干扰源或干扰源附近会增加连线的总干扰度。

位置 $A[x,y]$ 的干扰源的源干扰度为 $d(d>0)$ ，则连线的干扰度计算如下:

$1$ 、若连线经过位置 $A[x,y]$ ,则其总干扰度会增加d;

$2$ 、若连线经过离位置 $A[x,y]$ 距离小于 $d$ 的位置时，设其距离为 $K$ ，则总干扰度会增加 $(d-k)$ ;

$3$ 、若连线经过离位置A[x,y]距离大于或等于d的位置时，总干扰度不会增加;

注:

位置 $[x1,y1]$ 和位置 $[x2.y2]$ 之间距离的定义为: $|x1 -x2|$ + $|y1-y21|$ 。

如下 $3x3$ 矩阵，位置 $[1,1]$ 的源干扰度是 $2$ ，连线的位置序列为: $[0.0)->[0.1)->[0,2]->[1,2]>[2,2]$ 。

其中 $[0,1]$ 和 $[1,0]$ 到干扰源的距离为 $1$ ，会叠加 $1$ 的干扰度;其他位置到 $[1,1]$ 的距离均大于等于 $2$ ，所以不会叠加干扰度。

因此这条连线的总干扰度为 $2$

现在我们需要将左上角的器件到右下角的器件进行连线，两个器件的位置分别是左上角的 $[0.0]$ 和右下角的 $[M-1,N-1]$ 。由于我们希望连线尽量地短,从位置 $[0,0]$ 到 $[M-1,N-1]$ 的连线途中，我们规定连线只能向下或向右。

请根据输入( $M×N$ 的矩阵)，计算出连线的最小干扰度。

输入描述

第一行是两个整数 $M$ 和 $N$ ( $M$ 和 $N$ 最大值为 $1000$ )，表示行数和列数;

接着是 $M$ 行的数据，每一行包含 $N$ 个整数，代表每个位置的源干扰度，每个源干扰度小于 $50$

左上角[0,0]到右下角[M-1,N-1]连线的最小总干扰度。

输入

输出

说明

其中一条可以使干扰度最小的路径为: $[0.0]->[0.1]->[0.2]->[1.2]->[2,2]$ ，其干扰度为 $2$

输入

输出

说明

先从 $[0.0]$ 往下走到最下面 $[4.0]$ ，再往右走到右下角 $[4,4]$ ，途径 $[2,0]$ 时叠加了一个干扰度。

输入

输出

说明

先从 $[0.0]$ 往下走到最下面 $[4.0]$ ，再往右走到右下角 $[4,4]$ ，途径 $[2,0]$ 时叠加了一个干扰度。