Description
After many years of discipline and persistent practices, SuBaRaSi has almost become an otaku that
play Stepmania really well. However, to play even better, he needs to analyze the songs.
Many of rhythms have specifics patterns that SuBaRaSi can perform much easier because he is familiar with those patterns.
Note that he played Stepmania using his computer keyboard with both hands because it looks more like an otaku.
Since SuBaRaSi has learned the "technique of alternating left-right hands" from the "old-stubborn child", Zhou Buotong,
now he can play the songs using two hands independently without interfering other hand.
Patterns are described by strings consist of 0, 1, and 2. A zero means no taps, a one means a single tap on any
of the arrows, and a two means two taps simultaneously on any of two distinct arrows. For each pattern, either of his
hand could recognize it independently and apply it for playing more easily. Depending on the cost of the patterns, you
are going to help SuBaRaSi to develop an analysis such that he can use as small cost as possible to play the
song without any single miss or any extra taps.
Note that, the pattern with a single "0", "1" or "2" and their costs will be given in the input so that it is guaranteed that he can
perfectly play the song. The following is an example:
P1 = "0", cost 0
P2 = "1", cost 1
P3 = "2", cost 2
P4 = "121212", cost 2
P5 = "1012", cost 1
After the analysis:
Therefore, the cost for right hand is 2 + 1 + 0 + 2 = 5, and the cost for left hand is 1 + 0 + 1 + 1 + 0 = 3.
He needs totally 8 cost to play this song in this analysis.
Input
The input may consist of many cases. For each case, there are two integers p, l (3<=p<=20, 1<=l<=200) denoting
the number of patterns SuBaRaSi could recognize and the length of the song. In the each of following p lines, there
are a string Pi and an integer ci representing the patterns and cost of the patterns. Each Pi is consisted of digits 0, 1 or 2
and has length at most 10. The values of ci are all non-negative and less than 1000.
The following four lines describe the left, down, up, right arrows of the song. Each line is a string with length l and consisted
of 0 and 1. A 0 means the arrow does not appear, a 1 means the arrow is there.
Output
For each case, output exactly one number denoting the minimum cost SuBaRaSi can perform the song under any analysis.