1010. 幻灵战队 2

题目描述

“幻灵战队”是《金铲铲之战》S17 赛季中的一种娱乐羁绊。在本题中，我们简化了幻灵战队的机制：在开启了幻灵战队羁绊之后，玩家可以通过连败来获得科技点。河灵是一名幻灵战队宗师，他打算硬玩一把幻灵战队。该局游戏一共进行了 n 回合，河灵在游戏的开始就激活了幻灵战队羁绊（初始时科技点为 0），接下来的每个回合只有两种情况：

• 赢下了该场对战，此时不会获得科技点。

• 输掉了该场对战，假设玩家当前已经连败了 x 场（包含当前这场），则获得 20 + 5x 科技点。

现在，胖胖龙已经知道了河灵该局游戏 n 回合的胜负关系。胖胖龙作为河灵的死对头，当然希望河灵获得的科技点越少越好。为此，胖胖龙可以将该局游戏的至多 k 场失败对战篡改成胜利。篡改之后，河灵获得的科技点将按照修改过后的胜负关系重新计算。请你帮帮胖胖龙，使得河灵获得的科技点最少。你只需要求出这个最小的科技点即可。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 5 × 105 )，表示数据组数。对于每组测试数据：第一行两个整数 n, k (1 ≤ n ≤ 105, 0 ≤ k ≤ n)，表示该局游戏的回合数以及篡改的次数限制。第二行一个长度为 n 的 01 串，其中第 i 个字符表示第 i 个回合的胜负情况。若为 0 则表示失败，若为 1 则表示胜利。

保证所有测试数据中 n 之和不超过 5 × 105。

输出格式

对于每组测试数据：输出一行一个整数，表示答案。

样例输入

3
10 2
1010101010
11 2
00000000001
25 5
1001100100001100010010001

样例输出

75
235
285

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）