405296: GYM101875 E Loppinha, the boy who likes sopinha

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 K grams 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.

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 0 or 1, where 0 indicates a minute of rest and a 1 indicates a minute of workout.

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.

4 2
1101

1

10 5
1101100111

3

3 1
111

2

In the first test case, if he changes the second minute to rest, he will consume exactly 2 grams of protein. Notice that if he changes the last minute to rest instead, he would need 3 grams of protein to complete his workout session without dying.