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\).