#P0826. 快乐字符串

快乐字符串

题目描述

快乐字符串虽迟但到

给定一个长度为nn的二进制字符串 ss。

我们定义 did_i 为其十进制表示为 sisi+1s_i s_{i+1} 的数字(可能带有前导零)。我们定义 f(s)f(s) 为所有有效 did_i 的总和。换句话说,

f(s)=∑i=1n−1di.f(s) = \sum_{i=1}^{n-1} d_i.

例如,对于字符串 s=1011s = 1011:

  • d1=10d_1 = 10;
  • d2=01d_2 = 01;
  • d3=11d_3 = 11;
  • f(s)=10+01+11=22.f(s) = 10 + 01 + 11 = 22.

在一次操作中,你可以交换字符串中的任意两个相邻元素。如果允许最多 kk 次操作,我们定义所有可达字符串中f(s)f(s)最小的那些为快乐字符串,请找到快乐字符串,并输出 f(s)f(s) 的最小值。

输入格式

本题含有多组测试数据。

第一行输入一个整数 T(1≤T≤105)T(1 \le T \le 10^5),表示测试数据组数。

接下来对于每组测试数据,第一行输入两个整数 n,k(2≤n≤105,  0≤k≤109)n,k(2 \le n \le 10^5,\; 0 \le k \le 10^9)——字符串的长度和允许的最大操作次数。

第二行输入一个长度为 nn 的二进制字符串 ss,仅由00和11组成。

题目保证:在单个测试文件中∑n≤105\sum n \le 10^5。

输出格式

对于每组测试数据,输出一行一个整数,你可以执行最多 kk 次操作后 f(s)f(s) 的最小值。

样例

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

提示

对于第一组测试用例,你无法进行任何操作,因此快乐字符串就是 ss本身。f(s)=f(1010)=10+01+10=21f(s) = f(1010) = 10 + 01 + 10 = 21。

对于第二组测试用例,你可以获得的快乐字符串之一是"00110000011000",该字符串的ff值为2222。