题目描述

在幻想乡，比那名居天子是管理着『要石』的天人。『要石』是能够引发和镇压地震的存在，当然也可以用来改变地形。因为在幻想乡引发地震，而被灵梦等人教训了之后，天子不得不使用『要石』来修复地面。幻想乡可以视为长度为 N 个格子的一条横轴，其中有些格子的土地由于地震被破坏(记为 1)，有些格子则没有(记为 0)。每次使用『要石』，可以把一段长度为 L 的格子全部修复完成(即将 1 变为 0，L 覆盖的范围可以超出地图)，当然 L 越大，使用时所花费的灵力也就越多。天子希望最多使用 K 次『要石』就将所有被破坏的土地全部修复完成(即将 1 全部变为 0)，并且花费尽可能小的灵力。她想知道能够达到这个目的的 L 最小是多少。

输入格式

第 1 行：2 个整数，N, K
第 2 行：1 个 01 串，长度为 N

输出格式

第 1 行：1 个整数，L 的最小值

样例

输入

10 3
0101111011

输出

3

数据范围与提示

样例解释：0101111011 > 0000111011 > 00000000011  > 0000000000
对于 60%的数据：1 ≤ N,K ≤ 5,000
对于 100%的数据：1 ≤ N,K ≤ 500,000