该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个由 $n$ 个单元格组成的条带，所有单元格初始均为红色。

• 在一次操作中，你可以选择一个连续的单元格段并将其涂成蓝色。涂色前，所选单元格可以是红色或蓝色（注意不能将其涂成红色）。你最多可以进行 $k$ 次操作（可以是零次）。

同时给定一个字符串 $s$，若字符串第 $i$ 个字符（$1\leq i\leq |s|$）是字符 R，则代表期望该格子最终为红色，反之若为字符 B，则代表期望该格子最终是蓝色。

显然，有时无法在 $k$ 次操作内满足所有要求。因此，对于每个单元格，还指定了一个惩罚值，当该单元格在所有操作后呈现错误颜色时应用此惩罚。对于第 $i$ 个单元格，其惩罚值为 $a_i$。

最终涂色的惩罚值定义为所有错误颜色单元格的惩罚值的 最大值。如果没有错误颜色的单元格，惩罚值为 $0$。

求最大的惩罚值最小可能是多少？

输入格式

本题为多组数据

第一行包含一个整数 $t$，代表测试数据的数量。

• 每组数据第一行包含两个整数 $n$ 和 $k$（条带长度和最大操作次数）。

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

• 每组数据第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，代表每个单元格的惩罚值。

所有测试用例的 $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

提示

数据范围

对于 $100\%$ 的数据满足，$1\leq t\leq 10^4,1\leq n\leq 3\cdot 10^5,0\leq k\leq n,1\leq a_i\leq 10^9$。保证所有数据 $\sum n \leq 3\cdot 10^5$ 即所有组数据 $n$ 的和不超过 $3\cdot 10^5$。

• 子任务 $1$ （$10$ 分）：保证 $k=0$。
• 子任务 $2$ （$10$ 分）：保证 $k=n$。
• 子任务 $3$ （$30$ 分）：保证 $\sum n \leq 10^3$。
• 子任务 $4$ （$50$ 分）：无特殊限制。

样例解释

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

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

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