Competitive Fishing
Contest: Educational Codeforces Round 172 (Rated for Div. 2)
Difficulty rating: 1800
Tags: greedy

Alice and Bob participate in a fishing contest! In total, they caught $$$n$$$ fishes, numbered from $$$1$$$ to $$$n$$$ (the bigger the fish, the greater its index). Some of these fishes were caught by Alice, others — by Bob.

Their performance will be evaluated as follows. First, an integer $$$m$$$ will be chosen, and all fish will be split into $$$m$$$ non-empty groups. The first group should contain several (at least one) smallest fishes, the second group — several (at least one) next smallest fishes, and so on. Each fish should belong to exactly one group, and each group should be a contiguous subsegment of fishes. Note that the groups are numbered in exactly that order; for example, the fishes from the second group cannot be smaller than the fishes from the first group, since the first group contains the smallest fishes.

Then, each fish will be assigned a value according to its group index: each fish in the first group gets value equal to $$$0$$$, each fish in the second group gets value equal to $$$1$$$, and so on. So, each fish in the $$$i$$$-th group gets value equal to $$$(i-1)$$$.

The score of each contestant is simply the total value of all fishes that contestant caught.

You want Bob's score to exceed Alice's score by at least $$$k$$$ points. What is the minimum number of groups ($$$m$$$) you have to split the fishes into? If it is impossible, you should report that.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$).

The second line contains a string, consisting of exactly $$$n$$$ characters. The $$$i$$$-th character is either 0 (denoting that the $$$i$$$-th fish was caught by Alice) or 1 (denoting that the $$$i$$$-th fish was caught by Bob).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the minimum number of groups you have to split the fishes into; or -1 if it's impossible.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case of the example, you can split the fishes into groups as follows: the first three fishes form the $$$1$$$-st group, the last fish forms the $$$2$$$-nd group. Then, Bob's score will be $$$1$$$, and Alice's score will be $$$0$$$.

In the third test case of the example, you can split the fishes into groups as follows: the first fish forms the $$$1$$$-st group, the last three fishes form the $$$2$$$-nd group. Then, Bob's score will be $$$2$$$, and Alice's score will be $$$1$$$.

Example input:
7
4 1
1001
4 1
1010
4 1
0110
4 2
0110
6 3
001110
10 20
1111111111
5 11
11111

Example output:
2
-1
2
-1
3
4
-1

Editorial:
The main idea we need to solve this problem is the following one. For each fish, its value will be equal to the number of groups before its group. So, each "border" between two groups increases the value of every fish after the border by $$$1$$$.
Let $$$s_i$$$ be the number of Bob's fishes minus the number of Alice's fishes among the fishes with indices $$$i, i+1, \dots, n-1, n$$$; also, let $$$a_j$$$ be the index of the fish from which the $$$j$$$-th group starts.
Then the difference in scores between Bob and Alice is equal to $$$0 \cdot (s_{a_1} - s_{a_2}) + 1 \cdot (s_{a_2} - s_{a_3}) + \cdots + (m - 1) \cdot s_{a_m}$$$, where $$$m$$$ is the number of groups. This sum can be rewritten as: $$$0 \cdot s_{a_1} + (2 - 1) \cdot s_{a_2} + (3 - 2) \cdot s_{a_3} + \cdots + s_{a_m}$$$. So, $$$s_i$$$ denotes how the difference between Bob's score and Alice's score changes if we split the $$$i$$$-th fish and the $$$(i-1)$$$-th fish into different groups.
From this, it is clear that the final score is the sum of certain elements of the array $$$s$$$. Since we have to minimize the number of groups (the number of selected elements from the array $$$s$$$), it is optimal to choose the maximum elements.
So, the solution is the following: construct the array $$$s$$$, sort it, and take the next maximum element until the sum is less than $$$k$$$. The answer to the problem is the number of selected elements plus $$$1$$$.