Maximum Score by Merging a Binary String

You are given a binary string \(S\) of length \(n\) (each character is either '0' or '1'). You are also given an integer \(k\). In one operation, you may select any consecutive \(k\) characters in the string, and merge them into a new single character. When merging a substring \(T\) of length \(k\), you will obtain a certain score \(p\) and a new character \(c\). Both \(p\) and \(c\) are determined by the substring \(T\) according to a given mapping. After the merge, the substring of length \(k\) is replaced by the single character \(c\) (thus the string length decreases by \(k-1\)). You can repeat this operation as long as the current string length is at least \(k\).

Your task is to determine the maximum total score you can obtain by performing a sequence of merge operations.

Note: The mapping for every possible \(k\)-length binary substring is provided in the input. It is guaranteed that each of the \(2^k\) possible binary strings appears exactly once in the mapping.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \(n\) and \(k\) (\(1 \leq n \leq 15\) and \(2 \leq k \leq n\)).
2. The second line contains a binary string \(S\) of length \(n\) (each character is '0' or '1').
3. Then follow \(2^k\) lines. Each of these lines contains a binary string of length \(k\), a space, a character (either '0' or '1') representing the new character after merging, another space, and an integer score \(p\). This provides the mapping: merging the given \(k\)-length substring produces the specified new character and earns you score \(p\).

outputFormat

Output a single integer representing the maximum total score you can obtain.

sample

3 2
010
00 0 1
01 1 2
10 0 3
11 1 4

5