C. Спортивная рыбалка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб участвуют в соревновании по ловле рыбы! В общей сложности они поймали $$$n$$$ рыб, пронумерованных от $$$1$$$ до $$$n$$$ (чем больше рыба, тем больше ее индекс). Некоторые из этих рыб были пойманы Алисой, другие — Бобом.

Их результаты будут оцениваться следующим образом. Сначала будет выбрано целое число $$$m$$$, и все рыбы будут разделены на $$$m$$$ непустых групп. Первая группа должна содержать несколько (по крайней мере одну) самых маленьких рыб, вторая группа — несколько (по крайней мере одну) следующих по размеру рыб и так далее. Каждая рыба должна принадлежать ровно одной группе, и каждая группа должна являться непрерывным подотрезком рыб. Обратите внимание, что нумерацию групп менять нельзя: например, рыбы в первой группе не могут быть больше рыб во второй группе, потому что первая группа содержит несколько самых маленьких рыб.

Затем каждой рыбе будет присвоено значение в зависимости от индекса ее группы: каждая рыба в первой группе получает значение, равное $$$0$$$, каждая рыба во второй группе получает значение, равное $$$1$$$, и так далее. Таким образом, каждая рыба в $$$i$$$-й группе получает значение, равное $$$(i-1)$$$.

Счет каждого участника равен суммарному значению всех рыб, которые он поймал.

Вы хотите, чтобы счет Боба превышал счет Алисы не менее чем на $$$k$$$ очков. Какое минимальное количество групп ($$$m$$$) необходимо создать для разделения рыб? Если это невозможно, сообщите об этом.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$).

Вторая строка содержит строку, состоящую ровно из $$$n$$$ символов. $$$i$$$-й символ равен 0 (обозначает, что $$$i$$$-я рыба была поймана Алисой) или 1 (обозначает, что $$$i$$$-я рыба была поймана Бобом).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество групп, на которые нужно разделить рыб; или -1, если это невозможно.

Пример
Входные данные
7
4 1
1001
4 1
1010
4 1
0110
4 2
0110
6 3
001110
10 20
1111111111
5 11
11111
Выходные данные
2
-1
2
-1
3
4
-1
Примечание

В первом примере вы можете разделить рыб на группы следующим образом: первые три рыбы образуют $$$1$$$-ю группу, последняя рыба образует $$$2$$$-ю группу. Тогда счет Боба будет $$$1$$$, а счет Алисы будет $$$0$$$.

В третьем примере вы можете разделить рыб на группы следующим образом: первая рыба образует $$$1$$$-ю группу, последние три рыбы образуют $$$2$$$-ю группу. Тогда счет Боба будет $$$2$$$, а счет Алисы будет $$$1$$$.