题目描述

给你一个 $n\times n$ 的地图，地图上有 . 有 X。

求出最大的 $k$，使得：

在地图上能找到 $m(m\leq 2)$ 个 $1\times k$ 或 $k\times 1$ 的长条，使得长条不交且长条内全是 .。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，描述地图。

输出格式

一行一个非负整数，最大的 $k$。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

2 1
..
..

样例输出 #2

2

样例 #3

样例输入 #3

2 2
X.
..

样例输出 #3

1

样例 #4

样例输入 #4

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

样例输出 #4

5

样例 #5

样例输入 #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

样例输出 #5

10

提示

样例解释：

.X...
.XXXX
XX..2
111.2
.X.X2

对于所有数据，$1\leq n\leq1500$，$1\leq m\leq2$，地图上只有 . 和 X。