CF1691C.Sum of Substrings

You are given a binary string $s$ of length $n$.

Let's define $d_i$ as the number whose decimal representation is $s_i s_{i+1}$ (possibly, with a leading zero). We define $f(s)$ to be the sum of all the valid $d_i$. In other words, $f(s) = \sum\limits_{i=1}^{n-1} d_i$.

For example, for the string $s = 1011$:

• $d_1 = 10$ (ten);
• $d_2 = 01$ (one)
• $d_3 = 11$ (eleven);
• $f(s) = 10 + 01 + 11 = 22$.

In one operation you can swap any two adjacent elements of the string. Find the minimum value of $f(s)$ that can be achieved if at most $k$ operations are allowed.

给你一个长度为 $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)$ 的最小值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

First line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $0 \le k \le 10^9$) — the length of the string and the maximum number of operations allowed.

The second line of each test case contains the binary string $s$ of length $n$, consisting of only zeros and ones.

It is also given that sum of $n$ over all the test cases doesn't exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$0 \le k \le 10^9$）——分别表示字符串的长度和允许执行的最大操作次数。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，该字符串仅由字符 0 和 1 组成。

此外，保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, print the minimum value of $f(s)$ you can obtain with at most $k$ operations.

对于每个测试用例，输出在最多执行 $k$ 次操作的情况下所能得到的 $f(s)$ 的最小值。

• For the first example, you can't do any operation so the optimal string is $s$ itself. $f(s) = f(1010) = 10 + 01 + 10 = 21$.

• For the second example, one of the optimal strings you can obtain is "0011000". The string has an $f$ value of $22$.

• For the third example, one of the optimal strings you can obtain is "00011". The string has an $f$ value of $12$.

• 对于第一个样例，你无法执行任何操作，因此最优字符串即为 $s$ 本身。$f(s) = f(1010) = 10 + 01 + 10 = 21$。

• 对于第二个样例，你可以得到的最优字符串之一是 “0011000”。该字符串的 $f$ 值为 $22$。

• 对于第三个样例，你可以得到的最优字符串之一是 “00011”。该字符串的 $f$ 值为 $12$。