P3736 [HAOI2016] Character Merge

You are given a $01$ string of length $n$. Each time, you may merge $k$ adjacent characters to obtain a new character and gain a certain score. The resulting character and the score are determined by these $k$ characters. You need to find the maximum total score you can obtain.

The first line contains two integers, the string length $n$ and the parameter $k$. The second line contains $n$ space-separated characters, each either $0$ or $1$. The $i$-th character is the $i$-th character of the initial string. From the $3$-rd to the $(2^k + 2)$-th lines, each line contains one character and one integer. On line $(i + 2)$, the character $c_i$ is the resulting character for the $i$-th length-$k$ $01$ string when these $k$-bit strings are interpreted as binary numbers and ordered increasingly; the integer $w_i$ is the score for the corresponding $i$-th pattern.

Output a single integer denoting the answer.

Constraints - For $100\%$ of the testdata, it is guaranteed that: - $1 \leq n \leq 300$, $1 < k \leq 8$. - $c_i \in \{0, 1\}$, $1 \leq w_i \leq 10^9$. Translated by ChatGPT 5