提示: 欢迎访问OurACM平台。
Problem 1679 String Operation

Accept: 26    Submit: 162
Time Limit: 5000 mSec    Memory Limit : 98304 KB

Problem Description

In this problem, you are given a dictionary of words W.
The dictionary has N different word and each word in the dictionary has an integer value Vi (1≤i≤N).
And you are given another string S.
What you want to do is to select some words from W to form the string S.
There is something you should reminder:
  • Initially your value is zero.
  • You can choose the word for any times as your pleasure.
  • If you choose a word Wi, your value should add the corresponding value Vi.
  • The words you select can only be added one by one. So there should not be any overlap.
  • If you can not form the whole string S, you should get some penalty and your value should be subtracted by the number of character which you can not form times the penalty value P.
What is the maximum value you can get?

Input

The first line contains an integer C(C≤50), indicating the number of test cases. For each test case, the first line contains two integers W(0≤W≤10000) and P(0≤P≤10000), indicating the number of words in the dictionary and the penalty value. The following W lines, each line contains a word Wi and the corresponding integer value Vi (0≤Vi≤10000). The length of the word in the dictionary will not longer than 100, and the word only contains lower case character (‘a’-‘z’). The last line contains an not empty string S. The length of S will not longer than 10000, and only contains lower case character (‘a’-‘z’).

Output

For each test case, you have to output the maximum value you can get.

Sample Input

4 2 10 ac 5 m 10 acm 2 10 ic 5 p 7 icpc 3 5 fzu 10 uac 36 acm 10 fzuacm 2 10 ic 5 c 7 icpc

Sample Output

15 2 21 2

Source

FOJ月赛-2008年12月

Submit  Back  Status  Discuss