Given a bag full of rope segments, you will build the longest loop of rope while alternating colors. The bag contains $S$ segments and each segment will either be blue ($B$) or red ($R$). You are required to alternate between colors and because of this requirement you might not use every segment in the bag. If you only have segments of a single color, you will not be able to tie any knots and should output $0$. Each segment length is provided in centimeters and each knot in the loop consumes one centimeter of length from the loop. In other words, a knot consumes one-half of a centimeter from of the two segment it connects.
Note that pieces of string that have length 1, if used in making the cycle, might get reduced to just a pair of knots of total length 0. This is allowed, and each such piece counts as having been used.
The first line of input gives the number of cases, $N$. $N$ test cases follow. For each test case there will be:
One line containing the value $S$, the number of rope segments in the bag.
One line containing a space separated list of $S$ values. Each value $L$ indicates the segment length in centimeters followed by the letter $B$ or $R$ to indicate the segment color.
You may assume that $1 \leq S \leq 1000$ and $1 \leq L \leq 100$.
For each test case, output one line containing "Case #$x$: " followed by the maximum length of the rope loop that can be generated with the rope segments provided.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 5B 4 6R 1B 7R 3B 7 5B 4R 3R 2R 5R 4R 3R 2 20B 20R |
Case #1: 0 Case #2: 13 Case #3: 8 Case #4: 38 |