You are given a binary string of length $n$. You can merge $k$ adjacent characters into 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 score you can obtain.

Input

The first line contains two integers $n$ and $k$.

The next line contains a binary string of length $n$, representing the initial string.

The next $2^k$ lines each contain a character $c_i$ and an integer $w_i$, where $c_i$ is the resulting character obtained from the $i$-th merging scheme (corresponding to the $i$-th binary string of length $k$ when sorted in ascending order), and $w_i$ is the score obtained from that scheme.

Output

Output a single integer representing the answer.

Examples

Input 1

3 2
101
1 10
1 10
0 20
1 30

Output 1

40

Note

The 3rd to 6th lines represent the 4 merging schemes for binary strings of length 2. $00 \to 1$ gives 10 points, $01 \to 1$ gives 10 points, $10 \to 0$ gives 20 points, and $11 \to 1$ gives 30 points.

Constraints

For 100% of the data, $n \ge 1$, $0 \le c_i \le 1$, $w_i \ge 1$.