You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 同学喜欢查水表，这一天他来到了一条有 $N$ 个排成一列的水表的街道查水表。

经过鉴定，他发现有一些水表损坏了。其中水表的情况用 $01$ 串来表示，$0$ 表示水表没有损害，$1$ 表示水表损坏了。

• 例如，$0101$ 表示从左往右分别表示没有损坏的水表、损坏的水表、没有损坏的水表、损坏的水表。

小 Z 每次可以修复一段长度为 $L$ 的连续的水表（$L$ 覆盖的范围可以超出地图）。

小 Z 希望最多使用 $K$ 次修复操作就可以将所有损坏的水表全部修复完成。他想知道能够达到这个目的的 $L$ 最小值是多少。

输入格式

输入共两行。

第 $1$ 行：$2$ 个整数，$N, K$。

第 $2$ 行：$1$ 个 $01$ 串，$01$ 串长度为 N。

输出格式

输出共一行，$1$ 个整数，表示 $L$ 的最小值。

样例 #1

样例输入 #1

10 3
0101111011

样例输出 #1

3

样例 #2

样例输入 #2

5 1
11000

样例输出 #2

2

提示

【样例解释】

• 对于样例 $1$，$L$ 的最小值为 $3$，即每次修复长度为 $3$ 的连续水表，修复过程为 $0101111011 \rightarrow 0000111011 \rightarrow 00000000011 \rightarrow \rightarrow 0000000000$

• 对于样例 $2$，$L$ 的最小值为 $2$，即每次修复长度为 $2$ 的连续水表，修复过程为 $11000 \rightarrow 00000$

【数据范围】

对于前 $20\%$ 的数据，$1 \le N,K \le 50$。

对于前 $40\%$ 的数据，$1\le N,K \le 5,000$。

对于另外 $10\%$ 的数据，保证 $K = 1$。

对于另外 $10\%$ 的数据，保证 $K=N$。

对于 $100\%$ 的数据，$1 \le N,K \le 500,000$。