题目描述

题目译自 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$。

---

样例 1

输入

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

输出

3

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

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

---

样例 2

见附加文件下 bud1ocen.in 和 bud1ocen.out。

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

---

样例 3

见附加文件下 bud1ocen.in 和 bud2ocen.out。

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

---

样例 4

见附加文件下 bud3ocen.in 和 bud3ocen.out。

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

---

样例 5

见附加文件下 bud4ocen.in 和 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