给你一个长度为$$$n$$$的二进制字符串$$$s$$$。
让我们将 $$$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$$$。
在一次操作中,您可以交换字符串的任意两个相邻元素。求在最多允许 $$$k$$$ 操作的情况下可以实现的 $$$f(s)$$$ 的最小值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le k \le 10^9$$$) - 字符串的长度和允许的最大操作数。
每个测试用例的第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由零和一组成。
还假设所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印通过最多 $$$k$$$ 操作可以获得的 $$$f(s)$$$ 的最小值。
示例
输入 #1
3 4 0 1010 7 1 0010100 5 2 00110
输出 #1
21 22 12
注意
- 对于第一个示例,您无法执行任何操作,因此最佳字符串是 $$$s$$$ 本身。 $$$f(s) = f(1010) = 10 + 01 + 10 = 21$$$。
- 对于第二个示例,您可以获得的最佳字符串之一是“0011000”。该字符串的 $$$f$$$ 值为 $$$22$$$。
- 对于第三个示例,您可以获得的最佳字符串之一是“00011”。该字符串的 $$$f$$$ 值为 $$$12$$$。