题目内容

小明站在一个 $N \times M$ 的网格左上角 $(0,0)$，目标是走到右下角 $(N-1,M-1)$。他每次只能向右或向下移动一格，行和列的下标均从 $0$ 开始。

网格中每个格子有一个颜色值 $a_{ij}$，它是 $1$ 到 $C$ 之间的正整数。对于一条选定的路径，小明需要让路径上所有格子的最终颜色相同。他可以先选择一个目标颜色 $t$（$1 \le t \le C$），然后将该路径经过的每个格子都修改为颜色 $t$。将格子 $(i,j)$ 从原颜色 $a_{ij}$ 修改为 $t$ 的代价为 $|t - a_{ij}|$。一条路径的总修改代价就是路径上所有格子的修改代价之和。

请计算从左上角到右下角的所有合法路径中，总修改代价的最小可能值。

约束条件：

• 行数 $N$、列数 $M$、可选颜色数 $C$ 均满足 $1 \le N \le 50$，$1 \le M \le 50$，$1 \le C \le 50$。
• 每个格子的颜色值 $a_{ij}$ 满足 $1 \le a_{ij} \le C$。

输入描述

第一行包含三个整数 $N$、$M$、$C$，分别表示网格的行数、列数以及可选颜色数量。

接下来 $N$ 行，每行包含 $M$ 个整数，其中第 $i$ 行第 $j$ 个数表示格子 $(i,j)$ 的颜色值 $a_{ij}$。

输出描述

输出一个整数，表示从左上角到右下角的最小总修改代价。

样例1

输入

1 1 5
3

输出

0

说明

网格只有 1 个格子，路径只包含 $(0,0)$。选择目标颜色 3，修改代价为 $|3-3|=0$。由于格子颜色本来就是 3，不需要任何修改，所以最小总代价为 0。

样例2

输入

2 2 3
1 4
2 3

输出

2

说明

网格为 $\begin{matrix}1&4\\2&3\end{matrix}$。

从 $(0,0)$ 到 $(1,1)$ 有两条路径。选择目标颜色 2 时，先下后右经过 $(0,0)$、$(1,0)$、$(1,1)$，代价为 $|2-1|+|2-2|+|2-3|=1+0+1=2$；先右后下经过 $(0,0)$、$(0,1)$、$(1,1)$，代价为 $|2-1|+|2-4|+|2-3|=1+2+1=4$。因此目标颜色 2 下的更小代价为 2。

检查其他可选颜色：目标颜色 1 的最小代价为 3，目标颜色 3 的最小代价也为 3。所以总的最小修改代价为 2。

样例3

输入

1 4 5
2 5 1 4

输出

6

说明

网格只有一行，因此路径固定为 $(0,0)\to(0,1)\to(0,2)\to(0,3)$。

选择目标颜色 3 时，总代价为 $|3-2|+|3-5|+|3-1|+|3-4|=1+2+2+1=6$。

选择目标颜色 2 或 4 时，总代价同样为 6；而选择目标颜色 1 或 5 时，总代价为 8。因此最小总代价为 6。