CF1214D Treasure Island

我们都喜爱宝藏，对吧？这就是为何年轻的 Vasya 正在向一个宝藏岛进发。 宝藏岛可以看做一个 $n \times m$ 的矩阵，行从上到下标号为 $1\dots n$，列从左到右标号为 $1\dots m$。Vasya 现在在第 $1$ 行，第 $1$ 列，而宝藏位于第 $n$ 行，第 $m$ 列。 宝藏岛上有些位置是可以通过的空地，而其他位置是不可经过的丛林。 现在 Vasya 正急着寻找宝藏。他可以从第 $i$ 行，第 $j$ 列走到第 $i+1$ 行第 $j$ 列或第 $i$ 行第 $j+1$ 列，即可以向下或向右走。当然他不能通过丛林区域。 邪恶的女巫不想让 Vasya 得到宝藏。她可以用魔法使得一块空地变成丛林。当然，她不能对第 $1$ 行，第 $1$ 列或第 $n$ 行，第 $m$ 列施法。 请计算女巫至少需要将几块空地变成丛林，才能完全阻止 Vasya 获得宝藏。

第一行输入两个正整数 $n,m$，表示矩阵的行数和列数。 接下来 $n$ 行，每行 $m$ 个字符，描述宝藏岛。`.`代表空地，`#`代表丛林。

一个整数，表示 女巫至少需要将几块空地变成丛林。

### 样例解释 对于样例 $1$，这是一个可能的方案。  ### 数据范围 $3 \leq n \times m \leq 10^6$。