你是一只蚂蚁，但不是普通的蚂蚁——你是一只痴迷于奶酪学的蚂蚁！
你已经在厨房里发现了一块新的奶酪，并希望派遣尽可能多的部下（minions）去探索它。将这块奶酪想象成一个 $N$ 行 $M$ 列的表格，行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $M$。有些格子包含空洞，而另一些包含奶酪。我们将第 $r$ 行第 $s$ 列的格子记为 $(r, s)$。左上角和右下角的格子一定包含奶酪。
设部下的数量为 $K$。你的部下将从左上角的格子出发，在右下角的格子结束。他们只能向下或向右移动。此外，他们的路径不能“交叉”，这意味着我们可以给他们分配 $1$ 到 $K$ 的标签，使得不存在这样的格子：标签较小的部下从该格子向右离开，而标签较大的部下从该格子向下离开。
此外，你希望这些路径在某种意义上是“不同”的，即对于任意两个部下，都存在一个包含空洞的格子 $(r, s)$，使得其中一个部下在某个时刻处于第 $s$ 列且行号小于 $r$，而另一个部下在某个时刻（不一定同时）处于第 $s$ 列且行号大于 $r$。通俗地说，每一对部下都是从不同的侧面接近某个空洞的。
输出满足给定条件时 $K$ 的最大值。
一些不满足条件的路径示例：
(a) 无效的路径选择 - 它们相交 (b) 无效的路径选择 - 它们从同一侧接近空洞
输入格式
第一行包含正整数 $N, M$。
接下来的 $N$ 行包含表格行的描述。第 $i$ 行包含 $M$ 个字符，其中 . 表示奶酪，# 表示包含空洞的格子。
输出格式
输出 $K$ 的最大可能值，占一行。
子任务
在所有子任务中，$2 \le N, M \le 2000$。
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 15 | 所有空洞都在同一行。 |
| 2 | 18 | $N, M \le 10$ |
| 3 | 16 | $N, M \le 50$，第一行、最后一行、第一列或最后一列没有空洞。 |
| 4 | 18 | $N, M \le 50$ |
| 5 | 16 | $N, M \le 2000$，第一行、最后一行、第一列或最后一列没有空洞。 |
| 6 | 17 | 无附加限制。 |
样例
输入 1
5 5 ..... .#... ..... ...#. .....
输出 1
3
输入 2
5 5 ....# ....# ..... ..... #....
输出 2
1
输入 3
3 2 .# #. ..
输出 3
0
说明
第一和第二个样例的路径解释：
(a) 第一个样例的路径示例 (b) 第二个样例的路径示例