聪明海狸很注重自己的外表,并且特别注重鞋子,因此他拥有大量森林中最著名品牌的鞋子。他小心翼翼地处理自己的鞋子,让每一双鞋子都并排放置。但到了周末,由于他非常活跃的生活方式,更衣室变得一团糟。
ABBYY 的 Smart Beaver 不仅是该地区最聪明的海狸,而且也是最注重国内的。例如,每周一,聪明海狸都会清理家里的所有东西。
现在是星期一早上。聪明海狸不想花一整天的时间打扫卫生,而且还有很多事情要做,而且今天是健身房,所以他想尽快打扫干净。现在地板已经洗干净,灰尘也擦掉了——是时候清理更衣室了。但聪明海狸一进入更衣室,当天的所有计划就突然被破坏了:那里一片混乱,似乎根本无法处理,哪怕是一周。给我们的英雄一些希望:告诉他最少需要多少双鞋才能改变位置以使更衣室整洁。
更衣室是长方形的,被分成n×m个相等的方格,每个方格恰好包含一只鞋子。每双鞋都有一个唯一的编号,该编号是 1 到 $${ \frac { n \cdot m } { 2 } }$$ 之间的整数,更正式地说,坐标为 (i, j) 的正方形包含位于其上的一双鞋的整数。聪明的海狸相信,只有当每双运动鞋放在一起时,更衣室才是整洁的。我们假设正方形 (i1, j1) 和 (i2, j2) 中的一双运动鞋放在一起,如果 |i1 - i2| + |j1 - j2| = 1。
输入
第一行包含两个空格分隔的整数 n 和 m。它们与更衣室的大小相对应。接下来的 n 行每行包含 m 个空格分隔的整数。这些数字描述了更衣室。每个数字对应一个窃笑。
保证:
- n·m 是偶数。
- 与更衣室中鞋子的数量相对应的所有数字都将位于 1 和 $${ \frac { n \cdot m } { 2 } }$$ 之间。
- 从 1 到 $${ \frac { n \cdot m } { 2 } }$$ 的每个数字将恰好出现两次。
得分 30 分的输入限制为(子问题 C1):
- 2 ≤ n, m ≤ 8。
获得 100 分的输入限制为(子问题 C1+C2):
- 2 ≤ n, m ≤ 80。
输出
精确打印一个整数——需要改变位置的运动鞋的最少数量。
示例
输入 #1
2 3 1 1 2 2 3 3
输出 #1
2
输入 #2
3 4 1 3 2 6 2 1 5 6 4 4 5 3
输出 #2
4
注意
第二个样本。