D :: RNA Secondary Structure

Time Limit: 10 Seconds    Memory Limit: 65536 KB

RNA, which stands for Ribonucleic Acid, is one of the major macro molecules that are essential for all known forms of life. It is made up of a long chain of components called nucleotides. Each component is made up of one of 4 bases and are represented using A, C, G or U. The primary structure of RNA is a sequence of these characters. The secondary structure of RNA refers to the base pairing interactions between different components. More specifically, base A can pair up with base U and base C can pair up with base G. The stability of the RNA secondary structure depends on the total number of base pairs that can be formed. The final structure is the one that contains the maximum number of base pairs.

Let’s represent the primary structure as a string consisting of characters from the set (ACGU). The rules of secondary structure formation are as follows:

1. Any base A can form a pair with any base U
2. Any base C can form a pair with any base G
3. Each base can be part of at most one pair.
4. Let’s assume w < x, y < z and w < y. If base at index w forms a pair with base at index x and base at index y forms a pair with base at index z, then one of the following two conditions must be true: y > x , z < x
5. There can be at most K pairs between C and G.

 You will be given the primary structure of the RNA of a certain species and your job is to figure out the total number of base pairings in the final secondary structure based on the constraints mentioned above.

You will be given the primary structure in a compressed format that uses Run-length encoding. In this type of data compression, consecutive characters having the same value is replaced with a single character followed by its frequency. For example, “AAAACCGAAUUG” will be represented using “A4C2G1A2U2G1”. That means the primary structure will be  given in the format < c₁f₁c₂f₂c₃f₃...c_nf_n>, where c_i is from the set (ACGU) and f_i is a positive integer.

The species that we are dealing with have the following properties:

1. f1 + f2 + f3 + ...fn ≤ 10050
2. f1 ≤ 5000
3. fn ≤ 5000
4. f2 + f3 + f4 + ... + fn − 1 ≤ 50

Input

The first line of input is an integer T (T ≤ 200) that indicates the number of test cases. Each case contains two lines. The first line is the primary structure given in run-length encoded format. The second line gives you the value of K (0 ≤ K ≤ 20), that gives an upper limit on the number of C − G base pairs that can be in the final secondary structure.

Output

For each case, output the case number followed by the maximum number of base pairs that can be formed. Look at the samples for exact format.

 

One possible final secondary structure for case 1 is depicted below that shows the 6 base pairings.

Sample Input

3
A3C1G1C1U4A2U1
1
A3C1G1C1U4A2U1
0
A100U200
2

Sample Output

Case 1: 6
Case 2: 5
Case 3: 100

Submit

Source: SWERC 2012