题目背景

题目描述

给你一个 $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

样例 #6

样例输入 #6

见附件

样例输出 #6

531

提示

样例解释：

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

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

子任务编号	附加限制	分值
1	$m=1$	20
2	$n\leq 30$	22
3	$n\leq 300$	23
4		35