Description

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.

Input Format

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 Format

Output a single integer denoting the answer.

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

40

Hint

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