C. Sum of Substringstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputEach 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.OutputFor each test case, print the minimum value of f(s) you can obtain with at most k operations.ExampleInput
3
4 0
1010
7 1
0010100
5 2
00110
Output
21
22
12
Note  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. 
3
4 0
1010
7 1
0010100
5 2
00110

21 22 12 
['brute force', 'constructive algorithms', 'greedy', 'math', 'strings', '*1400']