C. Sum of Substrings
brute force; constructive algorithms; greedy; math; strings
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.
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.
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\).