比那名居天子

Problem 1

比那名居天子(tenshi.cpp/c/pas)

题目描述

在幻想乡，比那名居天子是管理着『要石』的天人。『要石』是能够引发和镇压地震的存在，当然也可以用来改变地形。因为在幻想乡引发地震，而被灵梦等人教训了之后，天子不得不使用『要石』来修复地面。幻想乡可以视为长度为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