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

Вам дана бинарная строка $$$s$$$ длины $$$n$$$.

Пусть $$$d_i$$$ — число, в десятичной системе счисления записываемое как $$$s_i s_{i+1}$$$ (возможно, с ведущим нулем). Определим $$$f(s)$$$ как сумму всех корректных значений $$$d_i$$$. Иными словами, $$$f(s) = \sum\limits_{i=1}^{n-1} d_i$$$.

Например, для строки $$$s = 1011$$$:

  • $$$d_1 = 10$$$ (десять);
  • $$$d_2 = 01$$$ (один);
  • $$$d_3 = 11$$$ (одиннадцать);
  • $$$f(s) = 10 + 01 + 11 = 22$$$.

За одну операцию вы можете поменять местами любые два соседних символа строки. Найдите минимально возможное значение $$$f(s)$$$, которое может быть получено после не более чем $$$k$$$ операций.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le k \le 10^9$$$) — длину строки и максимальное допустимое число операций.

Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую только из нулей и единиц.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите минимально возможное значение $$$f(s)$$$ после не более чем $$$k$$$ операций.

Пример
Входные данные
3
4 0
1010
7 1
0010100
5 2
00110
Выходные данные
21
22
12
Примечание
  • В первом примере делать операции нельзя, поэтому оптимальный ответ — сама строка $$$s$$$. $$$f(s) = f(1010) = 10 + 01 + 10 = 21$$$.
  • Во втором примере одно из оптимальных решений — строка «0011000». Для данной строки значение $$$f$$$ равно $$$22$$$.
  • В третьем примере одно из оптимальных решений — строка «00011». Для данной строки значение $$$f$$$ равно $$$12$$$.