题目描述

在古老的光暗迷宫中，每个房间都被永恒的魔法标记为光明（$1$）或黑暗（$0$）。冒险者小可需要从迷宫左上角的入口房间 $(1,1)$ 出发，前往右下角的出口房间 $(n,m)$，才能通过试炼。

迷宫的规则限制她每次只能向右或向下移动到一个相邻的房间。当她从一个房间踏入另一个房间时，如果两个房间的属性不同（即从光明踏入黑暗，或从黑暗踏入光明），她就必须消耗一点“灵魂能量”来稳定自身；如果属性相同，则无消耗。

小可的灵魂能量十分宝贵，她希望尽可能减少消耗。作为她的向导，请你根据已知的迷宫地图，计算出从入口到出口所需消耗的最少灵魂能量。

输入格式

第一行包含两个整数 $n$, $m$，表示迷宫的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数（$0$ 或 $1$），表示对应房间的属性。数字之间可以用空格分隔。

输出格式

输出一个整数，表示从房间 $(1,1)$ 到房间 $(n,m)$ 需要消耗的最少灵魂能量（即路径上相邻房间属性变化的最小次数）。

样例

3 3
0 0 1
1 0 1
1 1 0

2

样例解释

一条最优路径为：$(1,1)[0] \to (1,2)[0] \to (1,3)[1] \to (2,3)[1] \to (3,3)[0]$。

属性变化：$0\to0$（无消耗），$0\to1$（消耗 $1$），$1\to1$（无消耗），$1\to0$（消耗 $1$），总计消耗 $2$ 点能量。

数据范围

对于 $100\%$ 的数据，$1 \le n, m \le 1000$。