Background

Translated from XXXI Olimpiada Informatyczna - Stage I Budowa lotniska。

Problem Description

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 .。

Input Format

The first line contains two positive integers $n, m$。

The next $n$ lines describe the map。

Output Format

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

5 2
.X...
.XXXX
XX...
.....
.X.X.

3

2 1
..
..

2

2 2
X.
..

1

10 2
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
..........
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

5

10 2
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X

10

见附件

531

Hint

Explanation of the sample:

.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。

Translated by ChatGPT 5