有一个长度为 n n n 的 01 01 01 串，你可以每次将相邻的 k k k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k k k 个字符确定。你需要求出你能获得的最大分数。
输入格式
第一行两个整数 n,kn, kn,k。
接下来一行长度为 n n n 的 01 01 01 串，表示初始串。
接下来 2k 2k 2k 行，每行一个字符 cic_ici 和一个整数 wiw_iwi，ci c_i ci 表示长度为 k k k 的 01 01 01 串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符，wi w_i wi 表示对应的第 i i i 种方案获得的分数。