#Pqjdp19. 5.字符合并

5.字符合并

5.字符合并

题目描述

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

输入格式

第一行两个整数n,k。

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

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

输出格式

输出一个整数表示答案。

数据范围

(原站未提供,导入后需人工补齐)

样例

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分。

数据范围与提示

对于100%的数据,满足1<=n<=300,0<=ci<=1,2<=k<=8,1<=wi<=1090<=c_i<=1,2<=k<=8,1<=w_i<=10^9。