← 返回题目列表

Codeforces · 2070/C

C. 有限重涂

中文机器翻译题面 查看原题

给你一个条带,由 $$$n$$$ 个单元格组成,所有单元格最初都是红色的。

在一次操作中,您可以选择一段连续的单元格并绘制它们 蓝色。绘制之前,所选单元格可以是红色或蓝色。请注意,不可能将它们涂成红色。您最多可以执行 $$$k$$$ 操作(可能为零)。

对于每个单元格,指定所有操作后所需的颜色:红色或蓝色。

显然,并不总是能够满足 $$$k$$$ 操作中的所有要求。因此,对于每个单元格,还指定了惩罚,如果单元格在所有操作后最终颜色错误,则应用该惩罚。对于第 $$$i$$$ 个单元格,惩罚等于 $$$a_i$$$。

最终绘画的罚分计算为 最高处罚 在所有涂有错误颜色的单元格中。如果没有这样的单元格,则绘画惩罚等于$$$0$$$。

最终绘画可以达到的最低惩罚是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$0 \le k \le n$$$) — 条带的长度和最大操作数。

第二行包含一个字符串 $$$s$$$,由 $$$n$$$ 个字符组成 'R'和/或'B'. 'R' 表示单元格应涂成红色。 'B' 表示单元格应涂成蓝色。

第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 每个单元格的惩罚。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 最终绘画的最小惩罚。

示例

输入
复制

5
4 1
BRBR
9 3 5 4
4 1
BRBR
9 5 3 4
4 2
BRBR
9 3 5 4
10 2
BRBRBBRRBR
5 1 2 4 5 3 6 1 5 4
5 5
RRRRR
5 3 1 2 4

输出
复制

3
3
0
4
0

注意

在第一个测试用例中,您可以绘制从 $$$1$$$ 到 $$$3$$$ 的单元格。这幅画将是 BBBR。因此,只有单元格 $$$2$$$ 被涂上了错误的颜色。因此,对其的处罚是最终处罚,等于$$$3$$$。

在第二个测试用例中,绘画 BBBR 现在将导致 $$$5$$$ 的罚款。但是,如果将单元格从 $$$1$$$ 绘制到 $$$1$$$,则会导致 BRRR,那么只有单元格 $$$3$$$ 被涂上了错误的颜色。最终罚款为$$$3$$$。

在第三个测试用例中,您可以绘制从 $$$1$$$ 到 $$$1$$$ 以及从 $$$3$$$ 到 $$$3$$$ 的单元格。然后所有单元格都将是正确的颜色,惩罚等于 $$$0$$$。