您有一个包含 n 行和 n 列的网格。每个单元格要么是空的(用“.”表示),要么是阻塞的(用“X”表示)。
如果两个空单元共享一侧,则直接连接。如果存在以 (r1, c1) 开始、以 (r2, c2) 结束的空单元序列,且该序列中任意两个连续的单元直接相连,则两个单元 (r1, c1)(位于 r1 行和 c1 列)和 (r2, c2) 相连。连接组件是一组空单元,组件中的任何两个单元都连接,并且该组中没有单元连接到不在该组中的某个单元。
你的朋友 Limak 是一只大灰熊。他能够摧毁一定范围内的任何障碍。更准确地说,您可以在网格中选择一个大小为 k × k 的正方形,Limak 会将其中所有被阻挡的单元格转换为空单元格。但是,您只能请求 Limak 提供一次帮助。
所选方块必须完全位于网格内。利马克可能不会改变任何东西,因为无论如何所有单元格都是空的。
您喜欢大型连接组件。在 Limak 帮助您之后,网格中最大连通分量的最大可能尺寸是多少?
输入
输入的第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 500)——分别是网格的大小和 Limak 的范围。
接下来的 n 行中的每一行都包含一个包含 n 个字符的字符串,表示网格的第 i 行。每个字符都是“.”或“X”,分别表示空单元格或阻塞单元格。
输出
使用 Limak 的帮助后,打印最大连通分量的最大可能大小(单元格数量)。
示例
输入 #1
5 2 ..XXX XX.XX X.XXX X...X XXXX.
输出 #1
10
输入 #2
5 3 ..... .XXX. .XXX. .XXX. .....
输出 #2
25
注意
在第一个示例中,您可以选择大小为 2 × 2 的正方形。最好选择下图左图红框中的正方形。然后,您将得到一个包含 10 个单元的连接组件,在右图中标记为蓝色。