解题思路
先把题意转成更容易处理的形式。
一次压缩把一段长度为 k (k≥2) 的同字符连续子串压成 1 个新符号，所以：
- 原长度减少了 k−1
- 花费为 ak
P4714.第3题-压缩
题目内容
给定一个只包含 0 和 1 的字符串 s，长度为 n。你可以进行若干次“分段压缩”操作，每次操作规则如下：
- 选择一段由相同字符构成的连续子串，其长度为 k（k≥2）；
- 将其整体压缩为一个“特殊字符”（视为长度 1 的新符号，不再属于 0/1）；
- 一次压缩的代价为 a[k]；
- 被压缩过的段不允许再次参与压缩；不同压缩段不能重叠。
压缩与不压缩的段拼接后得到新的字符串，其长度等于“未压缩的原字符数量 + 压缩段的个数”。给定目标上限 m，要求将字符串长度压到恰好为 m 的同时，使总代价最小。若无法压到长度 m，输出 −1。
输入描述
每个测试文件均包含多组测试数据。第一行输入整数 T（1≤T≤102）。
对每组数据：
- 第一行输入两个整数 n,m（1≤n≤500，1≤m≤n）；
- 第二行输入一个长度为 n 的 01 串 s；
- 第三行输入 n 个整数 a1,a2,…,an（1≤ai≤109），表示压缩长度为 k 的段的代价为 ak。
保证所有测试中 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
