CF316C1.Tidying Up

Smart Beaver is careful about his appearance and pays special attention to shoes so he has a huge number of pairs of shoes from the most famous brands of the forest. He's trying to handle his shoes carefully so that each pair stood side by side. But by the end of the week because of his very active lifestyle in his dressing room becomes a mess.

Smart Beaver from ABBYY is not only the brightest beaver in the area, but he also is the most domestically oriented. For example, on Mondays the Smart Beaver cleans everything in his home.

It's Monday morning. Smart Beaver does not want to spend the whole day cleaning, besides, there is much in to do and it’s the gym day, so he wants to clean up as soon as possible. Now the floors are washed, the dust is wiped off — it’s time to clean up in the dressing room. But as soon as the Smart Beaver entered the dressing room, all plans for the day were suddenly destroyed: chaos reigned there and it seemed impossible to handle, even in a week. Give our hero some hope: tell him what is the minimum number of shoes need to change the position to make the dressing room neat.

The dressing room is rectangular and is divided into n × m equal squares, each square contains exactly one shoe. Each pair of shoes has a unique number that is integer from 1 to , more formally, a square with coordinates (i, j) contains an integer number of the pair which is lying on it. The Smart Beaver believes that the dressing room is neat only when each pair of sneakers lies together. We assume that the pair of sneakers in squares (_i_1, _j_1) and (_i_2, _j_2) lies together if |_i_1 - _i_2| + |_j_1 - _j_2| = 1.

聪明的海狸非常注重自己的外表，尤其关注鞋子，因此他拥有大量来自森林中最著名品牌的鞋履。他努力小心地摆放鞋子，使每双鞋都并排摆放。但由于他一周内极其活跃的生活方式，到了周末，他的更衣室便变得一片混乱。

来自ABBYY的聪明海狸不仅是当地最聪慧的海狸，也是最具家庭观念的海狸。例如，每逢周一，聪明的海狸都会彻底打扫自己家中的所有地方。

现在是周一早晨。聪明的海狸不想把一整天都花在打扫上；此外，他还有很多事情要做，而且今天还是健身日，因此他希望尽快完成整理工作。目前地板已经清洗完毕，灰尘也已擦拭干净——接下来该整理更衣室了。然而，聪明的海狸刚一踏入更衣室，他一整天的计划便瞬间化为泡影：那里一片混乱，看起来即使花上整整一周时间也难以收拾妥当。请给我们的英雄带来一丝希望：告诉他，最少需要移动多少只鞋子，才能让更衣室恢复整洁。

更衣室呈矩形，被划分为 $n \times m$ 个大小相等的方格，每个方格中恰好放置一只鞋子。每双鞋都有一个唯一的编号，该编号为从 $1$ 到 $\frac{nm}{2}$ 的整数；更准确地说，坐标为 $(i, j)$ 的方格中存放着一只属于编号为该整数之鞋对的鞋子。聪明的海狸认为，仅当每双鞋的两只鞋都彼此相邻时，更衣室才算整洁。我们定义：位于方格 $(i_1, j_1)$ 和 $(i_2, j_2)$ 中的两只鞋属于同一双鞋且彼此相邻，当且仅当 $|i_1 - i_2| + |j_1 - j_2| = 1$。

The first line contains two space-separated integers n and m. They correspond to the dressing room size. Next n lines contain m space-separated integers each. Those numbers describe the dressing room. Each number corresponds to a snicker.

It is guaranteed that:

• n·m is even.
• All numbers, corresponding to the numbers of pairs of shoes in the dressing room, will lie between 1 and .
• Each number from 1 to will occur exactly twice.

The input limits for scoring 30 points are (subproblem C1):

• 2 ≤ n, m ≤ 8.

The input limits for scoring 100 points are (subproblems C1+C2):

• 2 ≤ n, m ≤ 80.

第一行包含两个以空格分隔的整数 $n$ 和 $m$，分别表示更衣室的尺寸。接下来的 $n$ 行，每行包含 $m$ 个以空格分隔的整数，这些数字描述了更衣室的情况。每个数字对应一双运动鞋。

保证满足以下条件：

• $n \cdot m$ 为偶数；
• 更衣室内所有鞋子对编号对应的数字均在 $1$ 到 之间；
• 从 $1$ 到 的每个数字恰好出现两次。

获得 30 分的输入限制（子问题 C1）为：

• $2 \leq n, m \leq 8$。

获得 100 分的输入限制（子问题 C1 + C2）为：

• $2 \leq n, m \leq 80$。

Print exactly one integer — the minimum number of the sneakers that need to change their location.

输出一个整数——需要改变位置的运动鞋的最小数量。

The second sample.

第二个样例。