# COI 24 Sirologija

https://www.acmicpc.net/problem/31984

You are an ant, and not just any ant, but an ant obsessed with cheese!

You have discovered a new slice of cheese in the kitchen, and you want to send as many of your minions as possible to explore the cheese. We can imagine the cheese as a grid with $N$ rows and $M$ columns, where the rows are numbered from $1$ to $N$ from top to bottom, and the columns are numbered from $1$ to $M$ from left to right. Some cells contain holes, while the rest are cheese. The cell in the $r$-th row and $s$-th column will be denoted as $(r, s)$. The top-left cell and the bottom-right cell will surely contain cheese.

Let's denote the number of minions as $K$. Your minions will start their exploration in the top-left cell and finish in the bottom-right cell. They can only move down and right. Additionally, their paths must not "cross"; that is, we can assign them labels from $1$ to $K$ such that there is no cell from which a minion with a smaller label moved right while a minion with a larger label moved down.

Moreover, you want these paths to be "different" in some sense, meaning that for every two minions, there exists a cell $(r, s)$ containing a hole such that one of them was at some point in column $s$ and row with a label smaller than $r$, while the other was at some point (not necessarily the same) in column $s$ and row with a label greater than $r$. Informally, each pair of minions circumnavigated a hole from different sides.

Print the maximum value of $K$ such that there exists a selection of minion paths that satisfy the given conditions.

Some examples of paths that do not satisfy the conditions:

(a) they cross each other
(b) they navigate around the hole from the same side

## Input

In the first line are the natural numbers $N$ and $M$.

In the next $N$ lines are the descriptions of the rows of the grid. In the $i$-th row, there are $M$ characters where . represents cheese and # represents a hole.

## Output

In a single line, output the maximum possible value of the number $K$.

## Constraints and Subtasks

In all subproblems, it holds that $2 \le N, M \le 2000$.


### Sample Input 1

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

### Sample Output 1

`3`

### Sample Input 2

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

### Sample Output 2

`1`

### Sample Input 3

3 2
.#
#.
..

### Sample Output 3

`0`
### Explanation

In the first example, the largest $K$ is $3$. We can send three different groups of ants, each taking a different path that meets the given conditions.

In the second example, the largest $K$ is $1$. The holes in the grid make it impossible for more than one group to meet the conditions.

In the third example, the largest $K$ is $0$. There are too many holes that block all possible paths.

(a) Example of path choice from the first example
(b) Example of path choice from the second example