【题目描述】

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

【输入格式】

第一行两个整数n,k。

接下来一行长度为n的01串，表示初始串。输入的的相邻字符之间用一个空格隔开。

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

【输出格式】

输出一个整数表示答案。

【样例输入】

3 2
1 0 1
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%的数据，n≥1,0≤i≤1,wi**≥**1