该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 5B. 最后的机关

Limits

时间限制：2000ms

内存限制：256MB

Background

进入地下室后，引入眼帘的就是一个被笼子封住的宝箱和地上的许多踏板。这些踏板构成了一个 $n * m$ 的矩形，每个踏板都有自己的颜色。小周踩上了其中一个踏板，这个踏板突然就发出了光亮；但是小周在踏上了其他几个踏板之后，光亮又消失了。于是学者朱朱开始考察周围和环境和这些踏板，经过一段时间后，朱朱给出了自己的结论。

Description

对于同一种颜色的若干踏板，假设某一种颜色的踏板数量为 $k$ ($k>1$)，那么这 $k$ 个踏板需要被点亮 $k-1$ 次，此时称为完全点亮。点亮是需要成对进行操作的，那么这种颜色一共需要 $k*(k-1)/2$ 次操作。每次操作涉及到的两个踏板的坐标设为 $(r_1, c_1)$ 和 $(r_2, c_2)$，每走一步都需要在踏板上，需要找到通向这两块踏板的 最短路 ，才能将这两个踏板点亮 $1$ 次。将所有踏板完全点亮后才可以打开封住宝箱的笼子。

假设走一步需要 $1$ 的时间，小周想提前知道将所有踏板完全点亮需要多少时间，这样他可以考虑有没有必要去打开笼子。

提示：两块踏板之间的最短路即为两个点的曼哈顿距离，也就是说，点亮这两个踏板 $1$ 次需要的时间为 $|r_1-r_2| + |c_1-c_2|$.

Input

第一行两个整数 $n, m$ , 含义见背景；

下面 $n$ 行每行 $m$ 个整数，第 $i$ 行的第 $j$ 个整数 $c_{ij}$ 代表这个位置的踏板的颜色编号。

Output

输出一行，代表完全点亮所有踏板需要多少时间。

Samples

Sample Input

2 3
1 2 3
3 2 1

Sample Output

7

Data range

对于 50% 数据，$1 \le n \le m$, $n⋅m \le 1000$；

对于 100% 数据，$1 \le n \le m$, $n⋅m \le 100000$,颜色编号 $1 \le c_{ij} \le 100000$.