字符合并 - ROJ

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

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

输出一个整数表示答案。

【数据规模】

数据编号	$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$
$18$	$≤300$	$7$	$≤10^9$
$19$	$≤300$	$8$	$≤10^9$

对于100%的数据， $n≥1,0≤c_i≤1,w_i≥1$ 。