10439: #2063. 「HAOI2016」字符合并

内存限制：256 MB 时间限制：1.000 S 提交：0 解决：0
评测方式：文本比较 命题人：

题目描述

有一个长度为 n n n 的 01 01 01 串，你可以每次将相邻的 k k k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k k k 个字符确定。你需要求出你能获得的最大分数。

输入格式

第一行两个整数 n,kn, kn,k。

接下来一行长度为 n n n 的 01 01 01 串，表示初始串。

接下来 2k 2k 2k 行，每行一个字符 cic_ic​i​​ 和一个整数 wiw_iw​i​​，ci c_i c​i​​ 表示长度为 k k k 的 01 01 01 串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符，wi w_i w​i​​ 表示对应的第 i i i 种方案获得的分数。

输出格式

输出一个整数，表示答案。

样例

样例输入

3 2
101
1 10
1 10
0 20
1 30

样例输出

40

样例解释

第三行到第六行表示长度为 222 的四种 010101 串合并方案。00→100 \rightarrow 100→1 ，得 101010 分，01→101 \rightarrow 101→1，得 101010 分，10→010 \rightarrow 010→0 得 202020 分，11→111 \rightarrow 111→1 得 303030 分。

数据范围与提示

1≤n≤300, 0≤ci≤1, wi≥1, k≤8 1 \leq n \leq 300, \ 0 \leq c_i \leq 1, \ w_i \geq 1, \ k \leq 81≤n≤300, 0≤c​i​​≤1, w​i​​≥1, k≤8