EOJ-自适应编程学习平台

小木同学在设计一个密室逃脱游戏。

游戏的地图为一个$n*n$的正方形区域，共包含$n^2$个格子区域，以及编号从$1 \sim n$的$n$扇门。每个格子区域内可能包含最多一把钥匙，也可能不包含任何钥匙，当玩家找到开启所有门的钥匙时，即可逃出密室。

注意：每把钥匙只能开启一扇门，但可能存在多把钥匙可以开启同一扇门。

具体规则可以描述为：对于第$i$行第$j$列的格子区域包含一个数字$a_{i,j}$，如果：

• $a_{i,j}$为$1$，则该格子区域存在一把可以开启第$j$扇门的钥匙。
• $a_{i,j}$为0，则该格子区域不包含任何钥匙。

如下图所示：$a_{1,1}$、$a_{4,1}$格子藏有开启第$1$扇门的钥匙；$a_{2,2}$、$a_{3,2}$格子藏有开启第$2$扇门的钥匙；$a_{1,3}$格子藏有开启第$3$扇门的钥匙；$a_{3,4}$、$a_{4,4}$格子藏有开启第$4$扇门的钥匙；$a_{3,5}$格子藏有开启第$5$扇门的钥匙。

1 0 1 0 0
0 1 0 0 0
0 1 0 1 1
1 0 0 1 0
0 0 0 0 0

游戏设计完成后，小木同学感觉挑战难度偏低。于是他决定在地图上选择一块小为$k\times k$且四条边平行于地图边界的正方形区域，设置为障碍区。参与游戏的玩家将无法进入障碍区，也无法获得藏于该区域内的钥匙。

对于上述示例，小木看可以设置如下#所覆盖的$3\times 3$的区域为障碍区。

1 0 1 0 0
0 1 0 0 0
# # # 1 1
# # # 1 0
# # # 0 0

小木想知道，在确保游戏仍可玩的情况下（即障碍区之外仍然可以找到开启所有门的钥匙），他可以设置的障碍区最大是多少，请你帮他编程计算最大的$k$值。

第一行一个整数$n$（$n\le 100$）。

接下来$n$行，每行包含$n$个数字，数字均为$0$或者$1$。

一个整数$k$。