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

接下来一行长度为 $n$ 的 $01$ 串，表示初始串。

接下来 $2k$ 行，每行一个字符 cic_ic​i​​ 和一个整数 wiw_iw​i​​，ci c_i c​i​​ 表示长度为 $k$ 的 $01$ 串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符，wi w_i w​i​​ 表示对应的第 $i$ 种方案获得的分数。

输出一个整数，表示答案。

样例输入

3 2
101
1 10
1 10
0 20
1 30

样例输出

40

样例解释

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

1≤n≤300, 0≤ci≤1, wi≥1, k≤8 1 \leq n \leq 300, \ 0 \leq c_i \leq 1, \ w_i \geq 1, \ k \leq 81≤n≤300, 0≤c​i​​≤1, w​i​​≥1, k≤8