字符合并

题目描述

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

输入格式

第一行两个整数$n$，$k$。

接下来一行$n$个数，每个数为$0$或$1$，表示长度为$n$的$01$初始串。

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

输出格式

输出一个整数表示答案。

数据范围与提示

对于$100\%$的数据，满足$1 < n < 300$，$0 \leq c_{i} \leq 1$，$2 \leq k \leq 8$，$1 \leq w_{i} \leq 10^{9}$，数据存在梯度。

样例

3 2
1 0 1
1 10
1 10
0 20
1 30

40

说明

第$3$行到第$6$行表示长度为$2$的$4$种$01$串的合并方案。$00 \to 1$，得$10$分；$01 \to 1$，得$10$分；$10 \to 0$，得$20$分；$11 \to 1$，得$30$分。