Writing Robot

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.

2
3 2
2 2 hit
1 2 it
3 1 song
hitman
singasong
2 2
2 3 ab
1 6 ba
ababab
bababa

Case 1: 2
Case 2: 6

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.

Oneplus

2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT