题目描述

题目译自 XXXI Olimpiada Informatyczna – I etap Budowa lotniska

Bajtazar 正在设计一个新的机场，它将建在 Bajtocja 的中心。机场是一个 $n \times n$ 平方米的正方形，按照规划，它被划分为 $n^{2}$ 个 $1 \times 1$ 平方米的小方格。其中一些方格已经被计划的建筑物占据了（出发和到达大厅，空中交通管制塔，飞机库）。Bajtazar 的任务是为 $m\ (m \leq 2)$ 条同样长度的跑道找到合适的位置。

每条长度为 $k$ 的跑道必须由 $k$ 个相邻的空方格组成，形成一个 $1 \times k$ 或 $k \times 1$ 平方米的矩形。跑道之间不能相交，也不能包含被占据的方格。当两条跑道没有共同的格子时，我们说它们是不相交的。Bajtazar 想知道能够在机场上规划的跑道的最大长度是多少。

输入格式

第一行包含两个整数 $n,m\ (1 \leq n \leq 1500,1 \leq m \leq 2)$，分别表示机场的边长和要建造的跑道的数量。

接下来的 $n$ 行描述了机场的情况；每行有一个 $n$ 个字母组成的字符串，由 X（表示被占据的方格）和 .（表示空的方格）组成。

输出格式

输出一行一个整数 $k$，表示能够规划的跑道的最大长度。如果他不能规划出满足条件的跑道，则输出 $0$。

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

3

下图展示了一种可能的长度为 $3$ 的跑道的布局：

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

样例 2

见附加文件下 [bud1ocen.in](file:bud1ocen.in) 和 [bud1ocen.out](file:bud1ocen.out)。

该样例满足 $n=2, m=1$，所有的方格都是空的。答案是 $2$。

样例 3

见附加文件下 [bud2ocen.in](file:bud2ocen.in) 和 [bud2ocen.out](file:bud2ocen.out)。

该样例满足 $n=2, m=2$，有一个方格被占据了。答案是 $1$。

样例 4

见附加文件下 [bud3ocen.in](file:bud3ocen.in) 和 [bud3ocen.out](file:bud3ocen.out)。

该样例满足 $n=10, m=2$，除了第 $5$ 行，所有的方格都被占据了。答案是 $5$。

样例 5

见附加文件下 [bud4ocen.in](file:bud4ocen.in) 和 [bud4ocen.out](file:bud4ocen.out)。

该样例满足 $n=1500, m=2$，除了第 $31$ 列，所有的方格都被占据了，而第 $31$ 列只有 $2$ 个方格被占据了。答案是 $531$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

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