题目描述

请注意本题特殊的时间限制为 500ms。

学校要在一块 $n\times n$ 的方格场地上摆放若干张同样大小的正方形地垫。场地中有些格子已经被器材占用，不能被地垫覆盖，其余格子可以使用。

现在希望选定一个边长 $s$，并摆放至少 $m$ 张边长为 $s$ 的地垫。每张地垫必须完整覆盖一个 $s\times s$ 的方格区域，且区域内不能包含被占用的格子。不同地垫之间可以有重叠部分，但不能有两张地垫覆盖的格子集合完全相同。

请你求出满足要求的最大边长 $s$。如果不存在任何方案能摆放至少 $m$ 张地垫，输出 $-1$。

输入格式

第一行包含两个整数 $n,m$，分别表示场地边长和需要摆放的地垫数量。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串，仅包含字符 '.' 和 '#'：

• '.' 表示该格子可使用；
• '#' 表示该格子已被占用。

输出格式

输出一行一个整数，表示可以满足要求的最大正方形边长。若无法摆放至少 $m$ 张，输出 $-1$。

样例

5 6
.....
.....
..#..
.....
.....

2

2 1
##
##

-1

样例说明

第一组样例中，边长为 $2$ 的可用方形区域有 $12$ 个，不少于 $6$ 个；边长为 $3$ 时没有任何一个区域可用，所以答案为 $2$。

第二组样例中没有可使用的格子，因此无法摆放地垫。

数据范围

对于测试点 1～2，满足 $n <= 10$。

对于测试点 3～4，满足 $n <= 50$。

对于测试点 5～6，满足 $n <= 200$。

对于测试点 7～8，保证网格中没有障碍物。

对于测试点 9～10，保证 $m = 1$。

对于测试点 11～13，满足 $n <= 600$。

对于测试点 14～16，满足 $n <= 2000$，障碍物随机分布。

对于测试点 17～18，满足 $n <= 2000$，障碍物呈特殊结构分布。

对于测试点 19～20，满足 $n = 2000$。

对于所有测试点，满足 $1 <= n <= 2000$，$1 <= m <= n^2$。