题目描述

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

输入

第一行两个整数$n，k$。 接下来一行$n$个数字($0$或$1$)，表示初始串。 接下来$2k$行，第$i$行两个整数$c_i$和$w_i$，表示$i$写作二进制代表的$k$位字符合并后得到的新字符和分数。

输出

输出一个整数表示答案。

输入样例

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

输出样例

40

提示

【数据规模】

数据编号	$n$	$k$	$w_i$
$0$	$=10$	$2$	$≤10^5$
$1$	$=15$	$3$	$≤10^5$
$2$	$=20$	$4$	$≤10^5$
$3$	$=25$	$5$	$≤10^5$
$4$	$≤50$	$5$	$≤10^6$
$5$	$≤50$	$6$	$≤10^6$
$6$	$≤50$	$7$	$≤10^6$
$7$	$≤50$	$8$	$≤10^6$
$8$	$≤100$	$3$	$≤10^7$
$9$	$≤100$	$4$	$≤10^7$
$10$	$≤100$	$5$	$≤10^7$
$11$	$≤100$	$6$	$≤10^7$
$12$	$≤200$	$5$	$≤10^8$
$13$	$≤200$	$6$	$≤10^8$
$14$	$≤200$	$7$	$≤10^8$
$15$	$≤200$	$8$	$≤10^8$
$16$	$≤300$	$5$	$≤10^9$
$17$	$≤300$	$6$	$≤10^9$

<tr><td>$18$</td><td>$≤300$</td><td>$7$</td><td>$≤10^9$</td></tr><tr><td>$19$</td><td>$≤300$</td><td>$8$</td><td>$≤10^9$</td></tr></table>对于100%的数据，$n≥1,0≤c_i≤1,w_i≥1$。

规则表行号说明

表格覆盖全部k位二进制模式，共2^k行，第一行对应全0，最后一行对应全1；原文2k及第i行措辞省略了指数和0基编号。公开k=2样例按00、01、10、11依次对应可得到40，明确排除了从01开始的解释。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。