解题思路

先把题意转成更容易处理的形式。

一次压缩把一段长度为 $k\ (k\ge 2)$ 的同字符连续子串压成 $1$ 个新符号，所以：

• 原长度减少了 $k-1$
• 花费为 $a_k$

题目内容

给定一个只包含 $0$ 和 $1$ 的字符串 $s$，长度为 $n$。你可以进行若干次“分段压缩”操作，每次操作规则如下：

• 选择一段由相同字符构成的连续子串，其长度为 $k$（$k \ge 2$）；
• 将其整体压缩为一个“特殊字符”（视为长度 $1$ 的新符号，不再属于 $0/1$）；
• 一次压缩的代价为 $a[k]$；
• 被压缩过的段不允许再次参与压缩；不同压缩段不能重叠。

压缩与不压缩的段拼接后得到新的字符串，其长度等于“未压缩的原字符数量 + 压缩段的个数”。给定目标上限 $m$，要求将字符串长度压到恰好为 $m$ 的同时，使总代价最小。若无法压到长度 $m$，输出 $-1$。

输入描述

每个测试文件均包含多组测试数据。第一行输入整数 $T$（$1 \le T \le 10^2$）。 对每组数据：

• 第一行输入两个整数 $n,m$（$1 \le n \le 500$，$1 \le m \le n$）；
• 第二行输入一个长度为 $n$ 的 $01$ 串 $s$；
• 第三行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），表示压缩长度为 $k$ 的段的代价为 $a_k$。 保证所有测试中 $n$ 的总和不超过 $1000$。

输出描述

对每组数据输出一个整数，表示将字符串长度压到 $m$ 所需的最小代价；若无解，输出 $-1$。

样例1

输入

3
5 3
00111
3 5 7 9 11
4 2
0101
1 1 1 1
6 2
111000
10 2 5 10 20 50

输出

7
-1
10