#XMOJ11391. 魔法拉面摊

魔法拉面摊

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:noodle.in 输出文件:noodle.out

小明在学校门口摆了个拉面摊,他的招牌是「数字拉面」——每根面条上都刻着一个数字(0或1)。每天,他会把 $n$ 根刻着数字的面条排成一排,组成一个「面条串」。

一碗面的「魔力值」是这样算出来的:对于每一对相邻的面条,把它们看成十位和个位拼成的两位数,再把所有这样的两位数加起来。

比如面条串1011:三对相邻面条依次是10、01、11,分别算作 $10$、$1$、$11$,所以魔力值等于 $10+1+11=22$。

小明有个独门绝技:每次操作可以交换任意两根相邻面条的位置。但他一天最多只能施展 $k$ 次交换魔法。请你帮他算出,在最多 $k$ 次相邻交换之后,这碗拉面的魔力值最小能是多少。

输入格式

第一行一个整数 $t$,表示拉面配方的数量。

接下来每个配方占两行:第一行是两个整数 $n$、$k$,表示面条总数和最多交换次数;第二行是一个长度为 $n$ 的字符串,只含0和1,表示初始的面条排列。

输出格式

输出 $t$ 行,每行一个整数,表示对应配方在最多 $k$ 次相邻交换后能得到的最小魔力值。

样例

样例 1

3
4 0
1010
7 1
0010100
5 2
00110
21
22
12

样例说明:

第一组:k=0k=0,一次也交换不了,1010的三对依次是10、01、10,魔力值为 10+1+10=2110+1+10=21。

第二组:交换一次后,一种最优排列是0011000,六对依次是00、01、11、10、00、00,魔力值为 $0+1+11+10+0+0=22$。

第三组:交换两次后,一种最优排列是00011,四对依次是00、00、01、11,魔力值为 $0+0+1+11=12$。

样例 2

2
2 0
01
2 1
10
1
1

样例说明:

第一组:只有一对面条01,算作 11,交换次数为 00,魔力值是 11。

第二组:10交换一次变成01,魔力值从 $10$ 降到 $1$。

数据范围

$1 \le t \le 10^4$。

$2 \le n \le 10^5$,$0 \le k \le 10^9$。

题目保证所有配方的 $n$ 加起来不超过 $10^5$。

对于 $50\%$ 的测试点,$1 \le t \le 100$,$2 \le n \le 12$。

对于 $100\%$ 的测试点,$1 \le t \le 10^4$,$2 \le n \le 10^5$,且所有配方的 $n$ 之和不超过 $10^5$。