Cheap B-Subsequence
Some time ago, Dejan Stojanovic, a Serbian poet, said: “Words rich in meaning can be cheap in sound effects.” Is it true? A String Processing professor at UFPE wants to test this quote with strings. For that, he defined what he calls a “cheap B-subsequence”. A cheap B-subsequence, according to his definition, is a subsequence of size B, of a string S (B ≤ |S|), that has the lowest associated cost. To define the cost of a string, the professor determined a series of rules to each letter of the alphabet. The alphabet that he used contains only lowercase letters. The rule of a letter is defined as a set of pairs (Pi,Ci), which indicates that if this letter appears in a position X on the subsequence, where X is a multiple of Pi, then the cost of (X/Pi) ∗ Ci will be added to the total cost of this subsequence. Let’s show an example. Suppose we have the following rules:
[a] =
[b] =
[c] =
{(2, 3), (4, 10)} {(1, 4), (7, 50)} {(1, 2), (4, 20)}
[d..z] = { } // there are no rules for the characters ‘d’ to ‘z’
Suppose we have the string ‘abaabcbc’, and B = 4. If we choose the subsequence ‘aabc’ (abaabcbc),
we would do the following procedure to calculate the associated cost:
- The first letter of the sequence is an ‘a’, and the position 1 is neither multiple of 2 or 4, so the cost is 0;
- The second letter of the sequence is another ‘a’, and the position 2 is a multiple of 2, so we’ll add the cost of ( 2 ) ∗ 3 = 3;
- The third letter of the sequence is a ‘b’, and the position 3 is multiple of 1, so we will add the cost of ( 31 ) ∗ 4 = 12;
- The last letter of the sequence is a ‘c’, and the position 4 is a multiple of 1 and 4, so we will add the cost of ( 41 ) ∗ 2 + ( 4 ) ∗ 20 = 28.
The total associated cost to this subsequence is 43, which is not the lowest cost, since we could have chosen aaab (abaabcbc) and obtained an associated cost of 19 — this is indeed the cost of the cheap B-subsequence. Given the string S and the integer B, and the rules of the alphabet, your task is to create a program that tells the professor the cost of the cheap B-subsequence.
Input
The first line contains T (T ≤ 100) — the number of test cases, after this line T test cases follows. The first line of a test case contains a string S of lowercase letters and an integer B (1 ≤ B ≤ |S| ≤ 100). Each of the next 26 lines describe the rule of each letter. The first of the 26 lines corresponds to the rule of the letter ‘a’; the following line corresponds to the rule of the letter ‘b’; the last of the 26 lines corresponds to the rule of the letter ‘z’. Each line containing a rule is described in the following way: QP1 C1 P2 C2...PQ CQ (1≤Q≤10;1≤Pi ≤|S|;1≤Ci ≤50),whereQistheamountofpairs associated to this rule, and is followed by the pairs themselves.
2/2 Output
For each test case print a line containing ‘Case #X: and Y is the cost of the cheap B-subsequence.
Sample Input
2
abcd 1
1 1 20
1 1 15
118
1 1 30
112
0 (21 lines) abaabcbc 4
2 2 3 4 10
2 1 4 7 50
2 1 2 4 20
0 (23 lines)
Sample Output
Case #1: 8
Case #2: 19
Y ’, where X is the case number, starting at 1,