字符合并

题目描述

Y 同学手中有一个长度为 $n$ 的 $01$ 序列。他可以通过一种特定的“合并”操作来获取分数。

每次操作，Y 同学可以选择序列中相邻的 $k$ 个字符，将它们合并成一个新的字符（$0$ 或 $1$）。这次合并不仅会生成一个新字符，还会带来一定的分数奖励。生成的新字符和所获得的分数完全取决于这 $k$ 个相邻字符组成的状态。

具体来说，这 $k$ 个相邻字符可以看作一个长度为 $k$ 的二进制数。根据这个二进制数的值（从 $0$ 到 $2^k-1$），题目给定了 $2^k$ 种合并方案的规则，每种规则规定了该状态合并后生成的新字符 $c_i$ 以及获得的分数 $w_i$。

Y 同学可以不断进行合并操作，每次合并后，序列的长度会减少 $k-1$。他的目标是求出在最优的操作顺序下，他最终能够获得的最大总分数。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示初始 $01$ 序列的长度和每次合并的字符数量。

第二行包含 $n$ 个用空格隔开的字符，每个字符为 $0$ 或 $1$，表示初始的 $01$ 序列。

接下来 $2^k$ 行，每行包含一个字符 $c$ 和一个整数 $w$。这 $2^k$ 行依次对应长度为 $k$ 的 $01$ 串所表示的二进制数值从 $0$ 到 $2^k-1$ 的合并规则。即，第 $i$ 行（从这部分开始算，也就是整个输入的第 $i+2$ 行，对应二进制数 $i-1$）的 $c_{i-1}$ 表示该状态合并后的新字符，$w_{i-1}$ 表示该次合并获得的分数。

输出格式

输出一行一个整数，表示能够获得的最大分数。

样例

样例输入 #1

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

样例输出 #1

40

数据范围与约定

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

• $1 \le n \le 300$
• $1 < k \le 8$
• $c_i \in \{0, 1\}$
• $1 \le w_i \le 10^9$