Word´s combination is an interesting thing. Given a set of words S={s1, s2, ..., sn}, where si is a word only consists lowercase letter and its length is less than 50. When si merges in a text, its effect on reader´s mood is both positive and negative. A word´s positive effect is measured in love level li and negative effect is in hate level hi. At the same time, given a set paragraph P={P1, P2, ..., Pn} and Pj is a string whose length is less than 1000. For each word si in S, there is two conditions in Pj as follows: Related : si is a substring of Pj, and li units of love level is added to Pj, if si occurs several times in Pj, every occurrence is counted. Unrelated : si never occurs in Pj and this condition bring Pj nothing. Text T is defined as a subset of P. T´s love level is defined as sum of Pj´s love level where Pj belongs to T minus words´ hate level. Because a strange psychology phenomenon, hate level of a word which occurs in T is only counted once no matter how many times it occurs. Given the set of S and P, writing robot´s job is to select a subset T to maximum the love level.

The first line of the input contains a single integer T (1 ≤ T ≤ 15), the number of test cases. Then T cases follow. First line of each case contains 2 integers, S, P. (1≤S, P≤150), then S lines follows, each line contains 2 integers, li, hi, (1≤li≤100, 1≤hi≤1000), and a string si with length less than 50. Next P lines, each contains a string Pi with length less than 1000. It guarantees that the answer will not exceed 32-bit signed integer.

For the x-th test case, print "Case x: " and maximum T´s profit in a line.

In the first case, T maybe {""}, {"hitman"}, {"singasong"}, {"hitman", "singasong"} and their love level is 0, -1, 2, 1. So "singasong" is chosen. In the second case, cause "ab" and "ba" all occurs in P1 and P2, obviously choosing them both as T={"ababab", "bababa"} will get most love level.

multi