题目内容

小蓝有一排瓷砖，每块瓷砖颜色为红（用 R 表示）或蓝（用 B 表示）。他希望减少瓷砖的数量。一种操作称为“融合”：选择一段连续且颜色全部相同的瓷砖，长度为 $k$（$k \ge 2$），将这一段替换为一块“混合砖”，混合砖的图案消失，长度为 $1$。一次融合的代价为 $w_k$。融合得到的混合砖不能再参与后续融合，且不同融合段不能重叠。经过若干次融合后，整排瓷砖由未融合的原色砖和混合砖依次拼接而成。新的总长度等于未融合的原色砖数加上混合砖数。给定目标长度 $m$，在最终长度恰好为 $m$ 的条件下，请你计算最少需要花费的总代价。如果无法做到，输出 -1。

输入保证：瓷砖总数 $n \le 500$，目标长度 $m$ 满足 $1 \le m \le n$。所有测试数据中 $n$ 的总和不超过 $1000$。代价 $w_k$ 均为 $[1, 10^9]$ 内的整数。测试数据组数 $T \le 100$。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。接下来依次给出 $T$ 组数据。对于每组数据： 第一行包含两个整数 $n$ 和 $m$，用空格分隔。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 R 和 B 组成。 第三行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$，其中 $w_k$ 表示融合长度为 $k$ 的段所需的代价。

输出描述

对于每组测试数据，输出一行，包含一个整数，表示达到目标长度所需的最小总代价；如果无法达到，输出 -1。

样例1

输入

1
3 1
RRR
2 5 5

输出

5

说明

瓷砖序列为 RRR，长度为 $3$，目标长度 $m=1$。需要减少 $n-m=2$ 个字符。唯一连续段 RRR 长度为 $3$，只能通过一次融合长度为 $3$ 的段将其变为一块混合砖，减少 $2$ 个字符，代价为 $w_3=5$。因此最少总代价为 5。

样例2

输入

1
4 2
RBRB
1 5 10 20

输出

-1

说明

瓷砖序列为 RBRB，所有连续段长度均为 $1$。融合操作要求段长度 $k \ge 2$，因此无法进行任何融合。长度无法减少，无法从 $n=4$ 变为 $m=2$，输出 -1。

样例3

输入

1
6 3
RRBBRR
10 2 5 100 200 300

输出

6

说明

瓷砖序列为 RRBBRR，可拆分为三个连续段：RR（长度 $2$）、BB（长度 $2$）、RR（长度 $2$）。目标长度 $m=3$，需减少 $n-m=3$ 个字符。每个段只能通过融合长度为 $2$ 的段减少 $1$ 个字符，代价为 $w_2=2$。必须将三个段全部融合，总代价为 $2 \times 3 = 6$。因此最少总代价为 6。

样例4

输入

1
5 3
RRRRR
1 3 7 10 20

输出

6

说明

瓷砖序列为 RRRRR，是一个长度为 $5$ 的连续段。需要减少 $n-m=2$ 个字符。有以下几种方案：

• 融合一段长度为 $5$ 的段会减少 $4$ 个字符，超过需要的 $2$，无法恰好得到长度 $3$；
• 进行两次长度为 $2$ 的融合：先融合第 $1$ 到 $2$ 个 R（代价 $w_2=3$），再融合剩余原色砖中的第 $4$ 到 $5$ 个 R（代价 $w_2=3$）。两次融合不重叠，共减少 $2$ 个字符，总代价为 $3+3=6$；
• 融合一段长度为 $3$ 的段（代价 $w_3=7$）也减少 $2$ 个字符，但代价更高。 因此最少总代价为 6。