P9921 [POI 2023/2024 R1] Building an Airport

Translated from [XXXI Olimpiada Informatyczna - Stage I](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Budowa lotniska](https://sio2.mimuw.edu.pl/c/oi31-1/p/bud/)。

You are given an $n \times n$ map. The map contains `.` and `X`. Find the maximum $k$ such that: You can find $m$ $(m \leq 2)$ strips of size $1 \times k$ or $k \times 1$ on the map, such that the strips do not intersect, and every cell inside each strip is `.`。

The first line contains two positive integers $n, m$。 The next $n$ lines describe the map。

Output one non-negative integer in a single line: the maximum $k$。

Explanation of the sample: ```plain .X... .XXXX XX..2 111.2 .X.X2 ``` Constraints: for all testdata, $1 \leq n \leq 1500$, $1 \leq m \leq 2$, and the map contains only `.` and `X`。 | Subtask ID | Additional Constraints | Points | | :----------: | :----------: | :----------: | | 1 | $m = 1$ | 20 | | 2 | $n \leq 30$ | 22 | | 3 | $n \leq 300$ | 23 | | 4 | | 35 | Translated by ChatGPT 5