为了逃避顽皮的混乱制造者的滑稽行为,农夫约翰放弃了他的农场,前往玻维尼亚的另一边。在旅途中,他和他的 k 头奶牛决定住在豪华的 Grand Moo-dapest 酒店。酒店由 n 个连续排列的房间组成,其中一些房间已被占用。
农夫约翰想要为他和他的奶牛预订一组 k + 1 个当前空闲的房间。他希望他的奶牛尽可能安全,因此他希望尽量减少他的房间到奶牛房间的最大距离。房间 i 和 j 之间的距离定义为 |j - i|。通过计算这个最小可能距离来帮助农夫约翰保护他的奶牛。
输入
输入的第一行包含两个整数 n 和 k (1 ≤ k < n ≤ 100 000) - 酒店的房间数量以及与 Farmer John 同行的奶牛数量。
第二行包含描述房间的长度为 n 的字符串。如果第 i 个房间空闲,则字符串的第 i 个字符将为“0”;如果第 i 个房间被占用,则字符串的第 i 个字符将为“1”。保证该字符串中至少有 k + 1 个字符为“0”,因此至少存在 k + 1 个房间可供选择供 Farmer John 和他的奶牛入住。
输出
打印 Farmer John 的房间和他最远的奶牛之间的最小可能距离。
示例
输入 #1
7 2 0100100
输出 #1
2
输入 #2
5 1 01010
输出 #2
2
输入 #3
3 2 000
输出 #3
1
注意
在第一个示例中,Farmer John 可以为自己预订房间 3,为他的奶牛预订房间 1 和 4。到最远的牛的距离是 2。请注意,不可能使这个距离为 1,因为不存在三个连续的空闲房间的块。
在第二个示例中,Farmer John 可以为自己预订房间 1,为他的单头牛预订房间 3。他和他的牛之间的距离是 2。
在第三个示例中,Farmer John 预订了所有三个可用房间,并为自己保留了中间的房间,以便两头奶牛都在他旁边。他与最远的牛的距离是 1。