题目描述

有一个长度为$n$的$01$串，你可以每次将相邻的$k$个字符合并，得到一个新的字符并获得一定分数。

得到的新字符和分数由这$k$个字符确定。你需要求出你能获得的最大分数。

输入输出格式

输入格式

输入的第一行是两个整数，分别代表字符串长度$n$和参数$k$。

输入的第二行有$n$个用空格隔开的非零即一的字符，第$i$个字符表示初始串的第$i$个字符。。

第$3$到第$(2^k + 2)$行，每行有一个字符和一个整数，第$(i + 2)$行的字符$c_i$个整数$w_i$表示长度为$k$的$01$串连成二进制后按从小到大顺序得到的第$i$种合并方案得到的新字符,$w_i$表示对应的第$i$种方案对应获得的分数。

输出格式

输出一个整数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

40

说明/提示

数据规模与约定

对于$100\%$的数据，保证：

-$1\leq n\leq 300$，$1 \lt k \leq 8$。 -$c_i \in{0,1}$，$1 \leq w_i \leq 10^9$。