Problem Description

You are an ant, but not an ordinary one—you are an ant obsessed with cheeseology! You have discovered a new piece of cheese in the kitchen and wish to dispatch as many of your subordinates (little ants) as possible to explore it. Imagine this cheese as a grid with $N$ rows and $M$ columns, numbered from 1 to $N$ from top to bottom and from 1 to $M$ from left to right. Some areas have holes, while others contain cheese. We denote the area at the $r$-th row and $s$-th column as $(r, s)$. The top-left and bottom-right areas definitely contain cheese.

Let the number of subordinates be $K$. Your subordinates will start exploring from the top-left area and end at the bottom-right area. They can only move down or right. Additionally, their paths must not "cross," meaning we can assign them numbers from 1 to $K$ such that no subordinate moving right from a certain area has a lower number, while the subordinate moving down from that area has a higher number.

Furthermore, you want these paths to be "different" in a certain sense, i.e., for every pair of subordinates, there exists a hole area $(r, s)$ such that one subordinate is at the $s$-th column with a row number less than $r$ at some point, and the other subordinate is at the $s$-th column with a row number greater than $r$ at some point (not necessarily simultaneously). Informally, every pair of subordinates approaches the hole from different sides.

Output the maximum value of $K$ for the paths that satisfy the given conditions.

Here are some examples of paths that do not satisfy the conditions:

Input Format

The first line contains two positive integers $N, M$.

The next $N$ lines contain the description of each row. The $i$-th line contains $M$ characters, where . represents cheese and # represents a hole.

Output Format

Output the maximum value of $K$ for the paths that satisfy the given conditions.

Sample Input and Output

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

Notes

Data Range

• Subtask 1 (15 points): All holes are in the same row.
• Subtask 2 (18 points): $N, M \leq 10$.
• Subtask 3 (16 points): $N, M \leq 50$, and there are no holes in the first row, last row, first column, and last column.
• Subtask 4 (18 points): $N, M \leq 50$.
• Subtask 5 (16 points): $N, M \leq 2000$, and there are no holes in the first row, last row, first column, and last column.
• Subtask 6 (17 points): No additional constraints.

In all subtasks, $2 \leq N, M \leq 2000$.

见题面 Input 部分

见题面 Output 部分