#DP1089. 字符合并

字符合并

题目描述

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

输入格式

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

接下来一行长度为 nn0101 串,表示初始串。

接下来 2k2^k 行,每行一个字符 cic_i 和一个整数 wiw_icic_i 表示长度为 kk0101 串连成二进制后按从小到大顺序得到的第 ii 种合并方案得到的新字符,wiw_i 表示对应的第 ii 种方案获得的分数。

输出格式

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

样例

3 2
101
1 10
1 10
0 20
1 30
40

第三行到第六行表示长度为 22 的四种 0101 串合并方案。00100 \rightarrow 1 ,得 1010 分,01101 \rightarrow 1,得 1010 分,10010 \rightarrow 02020 分,11111 \rightarrow 13030 分。

数据范围与提示

$1 \leq n \leq 300, \ 0 \leq c_i \leq 1, 1\le w_i\le 10^9 , \ 2\le k \leq 8$