问题1238--倍增的烦恼

1238: 倍增的烦恼

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

题目背景

Rolnan要面对好多ddl,每个ddl都会让他烦恼,连续的ddl更是让他崩溃,所以他需要强大的LiuGod的帮助!

题目描述

接下来 \(n\) 天,有若干天会有ddl,其中,长度为 \(l\) 的连续的ddl给Rolnan带来的烦恼值是 \(\frac{l\cdot (l+1)}{2}\)。LiuGod可以施展任意次魔法,每次可以使任意一天的ddl消失。

例如:\(11101\) 带来的总的烦恼值为 \(\frac{3\cdot 4}{2}+\frac{1\cdot 2}{2}=6+1=7\)。

现在给定整数 \(k\) ,要求使得总的烦恼值不大于  \(k\) 。

输入

第一行两个整数\(n,k\),表示天数与烦恼界限值。

接下来一行一个长度为 \(n\) 的 \(01\) 字符串 \(S\) ,\(S_i=0\) 表示第 \(i\) 天没有ddl,\(S_i=1\) 表示第 \(i\) 天有ddl。

输出

输出一个整数,表示LiuGod最少需要施展魔法的次数。

样例输入 Copy

7 4
1110111

样例输出 Copy

2

提示

\(1\leq n \leq 10^5,1\leq k \leq 10^{18},S_i\in\{0,1\}\)