codeforces#P1691C. Sum of Substrings

    ID: 33005 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forceconstructive algorithmsgreedymathstrings*1400

Sum of Substrings

Description

You are given a binary string ss of length nn.

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

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

  • d1=10d_1 = 10 (ten);
  • d2=01d_2 = 01 (one)
  • d3=11d_3 = 11 (eleven);
  • f(s)=10+01+11=22f(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)f(s) that can be achieved if at most kk operations are allowed.

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

First line of each test case contains two integers nn and kk (2n1052 \le n \le 10^5, 0k1090 \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 ss of length nn, consisting of only zeros and ones.

It is also given that sum of nn over all the test cases doesn't exceed 10510^5.

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

Input

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

First line of each test case contains two integers nn and kk (2n1052 \le n \le 10^5, 0k1090 \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 ss of length nn, consisting of only zeros and ones.

It is also given that sum of nn over all the test cases doesn't exceed 10510^5.

Output

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

Samples

输入数据 1

3
4 0
1010
7 1
0010100
5 2
00110

输出数据 1

21
22
12

Note

  • For the first example, you can't do any operation so the optimal string is ss itself. f(s)=f(1010)=10+01+10=21f(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 ff value of 2222.
  • For the third example, one of the optimal strings you can obtain is "00011". The string has an ff value of 1212.