样例下载

题目描述

小明在黑板上写了一个长度为 $n$ 的 01 字符串，即每个字符要么是 0， 要么是 1。

给出一个参数 $m$，则长度为 $m$ 的 01 字符串共有 $2^m$ 个。将这 $2^m$ 个字符串按字典序从小到大排序，并依次编号为 $1, 2, ……, 2^m$。

小明可以进行以下操作：

对于黑板上的字符串，任意选择一个长度为 $m$ 的子串，如果其编号为 $i$，则将该子串擦除，替换为一个新的字符 $T_i$，并且得到 $V_i$ 的收益。

小明可以进行以上操作任意次，直到无法操作。每次操作的收益之和，则为小明的总收益。

问：小明该如何操作，可以使得总收益最大？你只需要输出小明可以得到的最大总收益。

输入格式

第一行：两个整数 $n, m$。

第二行：一个长度为 $n$ 的 01 字符串。

接下来 $2^m$ 行：

• 第 $i（1 ≤ i ≤ 2^m$）行包含一个字符 $T_i$ 和一个整数 $V_i$，表示编号为 $i$ 的字符串被替换成的字符和收益。

输出格式

一个整数，表示最大总收益。

样例输入

4 2
1011
1 1
0 2
1 3
0 10

样例输出

21

样例解释

1011 ---> 100 ：将 11 替换为 0，收益为 10

100 ---> 11 ：将 00 替换为 1，收益为 1

11 ---> 0 ：将 11 替换为 0，收益为 10

数据范围

$1 ≤ n ≤ 300; 1 < m ≤ 8; T_i\in\{0,1\}; 1 ≤ V_i ≤ 10^9$。