CF2070C.Limited Repainting

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个由 $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$ ）——条带长度和最大操作次数。

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

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

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

对于每个测试用例，输出一个整数——可达的最小总惩罚值。

输入#1

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

输出#1

第一个测试用例中，你可以将 $1$ 到 $3$ 号的单元格涂色。最终涂色为 BBBR。只有第 $2$ 号单元格颜色错误，因此总惩罚值为 $3$ 。

第二个测试用例中，若涂色为 BBBR 则总惩罚值为 $5$ 。但如果仅涂色 $1$ 号单元格得到 BRRR，则只有第 $3$ 号单元格颜色错误，总惩罚值为 $3$ 。

第三个测试用例中，可以分别涂色 $1$ 号单元格和 $3$ 号单元格。所有单元格颜色均正确，总惩罚值为 $0$ 。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?