Loppinha loves to go to the gym with his friends. He takes his training sessions very seriously, and he always follows his schedule very strictly. He just created a new plan where he has set exactly what he is going to do at every single one of the N minutes of the session.

Loppinha loves having a sopinha (small soup) before training. The soup contains Kgrams of protein. As you can imagine, he needs that protein to be able to endure his very tough exercises. He is burning protein at every minute he is working out, and the amount of protein he burns in a minute depends on how many minutes he has been working out without a minute of rest. If he has trained for p minutes without resting, in the (p + 1)-th minute of workout he is going to burn p + 1 grams of protein.

Of course, if he doesn't have enough protein at any moment he dies. For example, if he has 3 grams of protein at a moment and at that minute his workout requires 4, if he does the workout he dies. Given his schedule and the amount of protein K he has before starting the training session, Loppinha, who is willing to change some minutes of his workout, wants to know what is the minimum amount of minutes he has to change from working out to resting so he does not die.

Input

The first line of the input contains two integers N (1 ≤ N ≤ 450) and K (1 ≤ K ≤ 10⁷), indicating the number of minutes in Loppinha's training session and the amount of proteins in his soup. The next line contains a string with N characters, either 0or 1, where 0 indicates a minute of rest and a 1 indicates a minute of workout.

Output

Output a single integer - the minimum number of minutes Loppinha has to switch from workout to rest so that he can finish his exercises without dying.

题面大意是有一个长度为n的01串，每一段连续长度为x的1串的花费为a_1=1，d=1的等差数列和S_x。问把最少多少个1变成0，可以让总花费小于m。

第一眼看到题目很容易想到一个错误的想法：每次取最大的1段二分，这样每一刀肯定是性价比最高的。每次贪心的取性价比最高的分法。（这样肯定是最优的嘛

然后再想一下，有可能会有一些性价比没这么高的分法，但是恰好花费比m小，而性价比高的分法的花费可能会比m小很多。同时使前者的改变次数比后者少。

#include <bits/stdc++.h>

using namespace std;

const int maxn=505;
const int inf=1e9+7;

int n,m;
char str[maxn];
int dp[maxn][maxn];//dp[i][j]表示处理了前i个数字，还可以交换j次，还需要消耗的能量

int cal(int x)
{
    return x*(x+1)/2;
}

//递归的边界是刚好处理完n个数字，并且要求k>=0;
int DFS(int p,int k)//前p个数字换k次;
{
    if(k<0)
    {
        return inf;
    }
    if(k>=n)
    {
        return 0;
    }
    if(dp[p][k]!=-1)
    {
        return dp[p][k];
    }
    if(str[p]=='0')
    {
        return DFS(p+1,k);
    }
    dp[p][k]=inf;
    int i;
    for(i=p;i<n&&str[i]=='1';i++)
    {
        dp[p][k]=min(dp[p][k],DFS(i+1,k-1)+cal(i-p));
    }
    dp[p][k]=min(dp[p][k],DFS(i+1,k)+cal(i-p));
    return dp[p][k];
}

int main()
{
    scanf("%d %d",&n,&m);
    scanf("%s",str);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=n;i++)
    {
        if(DFS(0,i)<=m)
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}