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$$$:
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.
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$$$.
For each test case, print the minimum value of $$$f(s)$$$ you can obtain with at most $$$k$$$ operations.
34 010107 100101005 200110
21 22 12
Name |
---|