题目描述

考虑一个由 $H$ 行 $W$ 列的方格组成的网格。用 $(r, c)$ 表示从上到下第 $r$ 行、从左到右第 $c$ 列的方格。每个方格被涂成黑色或者白色。

当且仅当满足以下条件时，该网格被称为“好”的：

• 从 $(1, 1)$ 出发，我们可以通过向右或向下移动一个方格的方式，一直走到 $(H, W)$，而且始终停在一个白色的方格上。

需要注意的是，如果网格是“好的”，则 $(1, 1)$ 和 $(H, W)$ 必须是白色的。

你的任务是通过重复以下操作使网格变得“好”。找到完成任务所需的最小操作次数。可以证明，你始终可以在有限次操作内完成任务。

• 选择四个整数 $r_0, c_0, r_1, c_1(1 \\leq r_0 \\leq r_1 \\leq H, 1 \\leq c_0 \\leq c_1 \\leq W)$。对于每个 $r, c$ ($r_0 \\leq r \\leq r_1, c_0 \\leq c \\leq c_1$)，将 $(r, c)$ 的颜色取反，即白色变黑色，黑色变白色。

约束条件

• $2 \\leq H, W \\leq 100$

输入

输入以以下格式从标准输入中给出：

$H$ $W$ $s_{11} s_{12} \\cdots s_{1W}$ $s_{21} s_{22} \\cdots s_{2W}$ $\\vdots$ $s_{H1} s_{H2} \\cdots s_{HW}$

这里，$s_{rc}$ 表示 $(r, c)$ 的颜色 - # 表示黑色，. 表示白色。

输出

打印完成任务所需的最小操作次数。

示例输入 1

3 3
.##
.#.
##.

示例输出 1

1

进行操作 $(r_0, c_0, r_1, c_1) = (2, 2, 2, 2)$，只改变 $(2, 2)$ 的颜色，就可以完成任务。

示例输入 2

2 2
#.
.#

示例输出 2

2

示例输入 3

4 4
..##
#...
###.
###.

示例输出 3

0

不需要任何操作。

示例输入 4

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

示例输出 4

4