codeforces#P1691C. Sum of Substrings
Sum of Substrings
Description
You are given a binary string of length .
Let's define as the number whose decimal representation is (possibly, with a leading zero). We define to be the sum of all the valid . In other words, .
For example, for the string :
- (ten);
- (one)
- (eleven);
- .
In one operation you can swap any two adjacent elements of the string. Find the minimum value of that can be achieved if at most operations are allowed.
Each test contains multiple test cases. The first line contains the number of test cases (). Description of the test cases follows.
First line of each test case contains two integers and (, ) — the length of the string and the maximum number of operations allowed.
The second line of each test case contains the binary string of length , consisting of only zeros and ones.
It is also given that sum of over all the test cases doesn't exceed .
For each test case, print the minimum value of you can obtain with at most operations.
Input
Each test contains multiple test cases. The first line contains the number of test cases (). Description of the test cases follows.
First line of each test case contains two integers and (, ) — the length of the string and the maximum number of operations allowed.
The second line of each test case contains the binary string of length , consisting of only zeros and ones.
It is also given that sum of over all the test cases doesn't exceed .
Output
For each test case, print the minimum value of you can obtain with at most operations.
Samples
Note
- For the first example, you can't do any operation so the optimal string is itself. .
- For the second example, one of the optimal strings you can obtain is "0011000". The string has an value of .
- For the third example, one of the optimal strings you can obtain is "00011". The string has an value of .