题目描述

Eli 有一个 N 行 M 列的数字矩阵。每个格子里恰好有一个 0 到 9 之间的数字（含端点）。

她可以修改这个矩阵：把某个格子中的数字改成另一个数字。她可以修改若干个、全部，甚至一个也不改。把数字 X 改成数字 Y 需要花费 |X-Y| 秒，也就是两者的绝对差。

如果在矩阵中，存在一条由相邻（有公共边）格子组成、且所有格子数字都相同的路径，把上边界与下边界连起来，或者把左边界与右边界连起来，那么 Eli 就说她把矩阵的“两端连接起来”了。她希望同时做到这两件事：既连接上边界和下边界，也连接左边界和右边界。注意：为了做到这一点，两条路径必须使用同一个数字，因为两条路径一定会相交。

下面看一个例子：

示例矩阵说明

初始矩阵：

2753852
9567342
5294979
3180559

一种做法，花费 16 秒：

2753852
8888842
5284888
3180559

另一种做法，花费 14 秒，使用数字 3：

2753852
9333333
5394979
3380559

第三种做法，花费 14 秒，使用数字 7：

2753852
7777342
5297777
3180579

给定 Eli 的初始矩阵，你能求出她把矩阵两端按要求连通所需的最少时间吗？

输入格式

第一行输入两个整数 N 和 M。
接下来 N 行，每行输入一个长度为 M 的数字串。

输出格式

输出一个整数，表示按要求修改矩阵所需的最少秒数。

约束

• 1 ≤ N, M ≤ 500
• 子任务 1：占 40% 分值，N, M ≤ 200
• 子任务 2：占 40% 分值，至少存在一个最优解，使得两条路径恰好只在一个格子相交
• 子任务 1 与子任务 2 合计占 60% 分值
• 测试按每 5 个测试点分组；一组的分数只有在该组内所有测试全部通过时才能获得

样例

输入

4 7
2753852
9567342
5294979
3180559

输出

14