This is just another word game. You are given a dictionary of words. Each of the word has a weight W, which is an integer value. You are given another string S. Initially your score is zero. In each turn you can mark some consecutive characters. If these consecutive characters create a word in the given dictionary, corresponding weight will be added to your score, otherwise a penalty P will be subtracted word length times from your score. Here word length is number of character in a word, and P is an integer value. What is the maximum score you can gain? Note that your have to make a move until all characters of S are marked, and you cannot mark one character more than once. Input Input will start with an integer number T (T ≤ 20), which indicates the number of test case. Each test case starts with two integer N (N ≤ 10000) and P (0 ≤ P ≤ 10000). Here N is the number of words in the dictionary and P is the value of Penalty. Each of the next N lines will contain a word and corresponding integer weight W (0 ≤ W ≤ 10000). No word of this dictionary will contain more than 100 characters, and a word will only contain lower case alphabet (‘a’, ‘b’, . . . , ‘z’). The last line of the input will contain string S. S will not contain more than 10000 characters, and will contain only lower case letters. Output For each test case you have to output one line which ‘Case #:’ where # is replaced by the case number, then a space, then the maximum score. Sample Input 3 25 ab 2 cd 3 abcd 35 ab 2 cd 3 bc 16 abcd 1 100 abd 1 abcd Sample Output Case 1: 5 Case 2: 6 Case 3: -400