小慕正在设计一块电路板，板上需要布置多个器件之间的连线。为了避免信号受到干扰，他希望找到一条干扰最小的路径。 小慕将电路板简化为一个 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 - y2|。 例如，在一个 3×3 的矩阵中，位置 [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]。为了尽量缩短连线长度，规定连线只能向下或向右移动。 请根据输入的 M × N 矩阵，计算出连线的最小干扰度。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行是两个整数M和N(M和N最大值为1000)，表示行数和列数； 接着是M行的数据，每一包含N个整数，代表每个位置的源干扰度，每个源干扰度小于50。
输出描述
左上角[0,0]到右下角[M-1,N-1]连线的最小总干扰度。
示例
示例 1
输入
5 5 0 0 0 0 0 0 0 2 0 0 0 2 0 2 0 0 0 2 0 0 0 0 0 0 0
输出
2
时间限制 1000 ms · 内存限制 128 MB