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~.