题目描述

$CRY$ 带着 $k$ 个妹子去酒店住宿。酒店的房间分布表示为一张 $n \times m$ 的网格图，每个房间用 $0$ 表示该房间可以入住，$1$ 表示该房间不能入住。正直的 $CRY$ 开了 $k+1$ 间房间，但是 $CRY$ 希望能尽量地靠近所有妹子。具体地，他希望自己他到所有妹子切比雪夫距离的最大值最小。数据保证的 $0$ 的个数一定大于等于$k+1$。

注：两点 $(x_1,y_1)\ (x_2,y_2)$ 的切比雪夫距离为 $max(abs(x_1-x_2),abs(y_1-y_2))$ ，其中 $abs()$为绝对值函数。

输入格式

第一行三个数 $n，m，k(1\leq n，m\leq 10^3，1\leq k\leq 10^6)$。

下面 $n$ 行，每行一个长度为 $m$ 的 01 串。

输入数据保证不会出现住不下的情况。

输出格式

一行一个数字代表最小化的结果。

样例

输入样例

2 5 3
01100
11100

输出样例

1

数据范围与提示

请注意，变量名 y1 和某些版本的 C++ 标准库中的某个变量名称可能产生冲突。

实际上该情况在 Windows 下与 Linux 的后果也不相同。