HDU OJ ACM Font Size:← →Problem DescriptionWord's combinatio

HDU OJ ACM
Font Size:← →
Problem Description
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.
Input
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.
Output
For the x-th test case,print "Case x:" and maximum T's profit in a line.Sample Input
2
3 2
2 2 hit
1 2 it
3 1 song
hitman
singasong
2 2
2 3 ab
1 6 ba
ababab
bababa
Sample Output
Case 1:2
Case 2:6

很明显的字典树题目.呵呵
这个你直接百度题号,连解题报告都有了