BZPRO

#4565. [Haoi2016]字符合并

内存限制：256 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述

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

输入格式

第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2k行，每行一个字符ci和一个整数wi，ci
表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应
获得的分数。1<=n<=300,0<=ci<=1,wi>=1,k<=8

输出格式

输出一个整数表示答案

样例

样例输入


			
3 2

101

1 10

1 10

0 20

1 30

样例输出


			
40

//第3行到第6行表示长度为2的4种01串合并方案。00->1,得10分，01->1得10分，10->0得20分，11->1得30分。

数据范围与提示

BZPRO Powered by Remmina.
Github Repository