Bob is learning binary numbers. To help Bob memorize the first $2^k$ (from $0$ to $2^k-1$) binary representations, his teacher, Mr. Ecurb, designs a binary game. In this game, Bob is given a binary sequence $S$, which only consists of 0 and 1, and $2^k$ substitution rules, where the $i^{th}$ rule ($0\le i\le 2^k-1$) replaces number $i$'s $k$-bit binary representation with character $c_i$ ($c_i=0\text{ or }1$) and generates value $v_i$. If number $i$'s $k$-bit binary representation occurs in the sequence $S$, Bob can apply this rule to replace it with character $c_i$ and get value $v_i$. Bob's objective is to achieve the maximum value by using these substitution rules on $S$. Can you write a program to help Bob?

Constraints

For all subtasks:

$1\le |S|\le 300$

$2\le k\le 8$

Subtask	Points	Additional constraints
$1$	$28$	$1\le |S|\le 50$
$2$	$32$	$1\le |S|\le 200$
$3$	$40$	No additional constraints.

Input Specification

The first line contains two integers, $|S|$ and $k$, the length of the binary sequence and the length of the binary representation.

The second line contains a binary sequence, $S$.

$2^k$ lines of input follow. The $i^{th}$ line contains two integers, $c_i$ and $v_i$, a substitution rule to convert the number $i$'s $k$-bit binary representation to character $c_i$ with value $v_i$, ($c_i=0\text{ or }1$, $1\le v_i\le {10}^9$).

Output Specification

Print one integer, the maximum value Bob can achieve by using the substitution rules on sequence $S$.

Sample Input

3 2
101
1 8
1 8
0 16
1 30

Sample Output

38

Explanation of Sample Output

There are $4$ substitution rules:

• Rule 1 replaces binary representation $00$ with $1$ to get value $8$
• Rule 2 replaces binary representation $01$ with $1$ to get value $8$
• Rule 3 replaces binary representation $10$ with $0$ to get value $16$
• Rule 4 replaces binary representation $11$ with $1$ to get value $30$

For the input sequence $101$, Bob can use Rule 2 to convert $S$ to $11$ with value $8$ and then use Rule 4 to convert $11$ to $1$ to get value $30$. The total value is $38$.