#2063. 「HAOI2016」字符合并

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

输入格式

第一行两个整数 n, k

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

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

输出格式

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

样例

样例输入

3 2
101
1 10
1 10
0 20
1 30

样例输出

40

样例解释

第三行到第六行表示长度为 2 的四种 01 串合并方案。 00 \rightarrow 1 ,得 10 分, 01 \rightarrow 1 ,得 10 分, 10 \rightarrow 0 20 分, 11 \rightarrow 1 30 分。

数据范围与提示

1 \leq n \leq 300, \ 0 \leq c_i \leq 1, \ w_i \geq 1, \ k \leq 8