Closing the Loop (Small)

Interview

Time limit5sMemory limit512 MB

Summary

Pick equal numbers of red and blue segments with the largest lengths and subtract one centimeter per knot to get the longest alternating loop.

Level: Medium4 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

A bag holds $S$ rope segments. Each segment is blue (B) or red (R), and its length is an integer number of centimeters. You tie segments together into one closed loop, and the colors must alternate all the way around the loop. Because of that rule you do not have to use every segment in the bag. If the bag holds only one color, no knot can be tied and the answer is 0.

Each knot shortens the loop by one centimeter, taking half a centimeter from each of the two segments it joins. A loop built from $m$ segments has $m$ knots, so it loses $m$ centimeters in total. The smallest possible loop is two segments joined by two knots.

A segment of length 1 may give all of its length to its two knots and leave 0 centimeters behind. That is allowed, and such a segment still counts as used.

Find the greatest loop length you can build.

Input

The first line contains $N$ , the number of test cases.

Each test case takes two lines. The first line contains $S$ , the number of rope segments. The second line contains $S$ space separated values. Each value is an integer length $L$ followed immediately by the letter B or R giving the color.

Limits

$1 \le N \le 5$
$1 \le S \le 1000$
$1 \le L \le 100$

Output

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting at 1 and $y$ is the maximum loop length.

Examples2

Example 1

Input

4
1
5B
4
6R 1B 7R 3B
7
5B 4R 3R 2R 5R 4R 3R
2
20B 20R

Expected output

Case #1: 0
Case #2: 13
Case #3: 8
Case #4: 38

Example 2
Input
```
1
2
1B 1R
```
Expected output
```
Case #1: 0
```