Вам дана бинарная строка \(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\):
За одну операцию вы можете поменять местами любые два соседних символа строки. Найдите минимально возможное значение \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач