Polycarp 的工作日正好持续 $$$n$$$ 分钟。他喜欢巧克力,并且可以在一分钟内吃掉一根巧克力。今天,Polycarp 在工作日开始时有 $$$k$$$ 酒吧。
工作日的某些分钟里,波利卡普有重要的事情要做,而在这些分钟里他无法吃巧克力棒。在其他几分钟内,他可以吃或不吃一块巧克力。可以保证的是,在工作日的第一分钟和最后几分钟,波利卡普没有什么重要的事情要做,他总是会在这几分钟里吃酒吧,让自己在工作日开始和结束时感到高兴。还可以保证 $$$k$$$ 严格大于 $$$1$$$。
你的任务是确定吃巧克力棒的顺序,使吃巧克力棒之间的最大休息时间尽可能短。
考虑 Polycarp 在 $$$x$$$ 分钟内吃了一个酒吧,并在 $$$y$$$ 分钟内吃了下一个酒吧 ($$$x < y$$$)。那么休息时间等于 $$$y - x - 1$$$ 分钟。波利卡普没有必要吃掉他拥有的所有金条。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 200\,000$$$, $$$2 \le k \le n$$$) — 工作日的长度(以分钟为单位)以及 Polycarp 在工作日开始时拥有的巧克力棒的数量。
第二行包含长度为 $$$n$$$ 的字符串,由零和一组成。如果字符串中的第 $$$i$$$ 个符号等于 0,则波利卡普在 $$$i$$$ 分钟内没有重要的事情要做,他可以吃一块巧克力。在另一种情况下,波利卡普现在正忙着$$$i$$$,无法吃一块巧克力。可以保证字符串的第一个和最后一个字符等于零,并且波利卡普在这几分钟内总是吃巧克力棒。
输出
打印吃巧克力棒之间可能的最短休息时间(以分钟为单位)。
示例
输入 #1
3 3 010
输出 #1
1
输入 #2
8 3 01010110
输出 #2
3
注意
在第一个示例中,Polycarp 无法在第二分钟内吃掉巧克力棒,因此休息时间等于一分钟。
在第二个示例中,Polycarp 无论如何都会在 $$$1$$$ 分钟和 $$$8$$$ 分钟内吃掉巧克力棒,而且他还需要在 $$$5$$$ 分钟内吃掉巧克力棒,因此最大休息时间将等于 $$$3$$$ 分钟。