### Problem

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.

### Input

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.

### Output

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.

### Limits

1 ≤ number of rope segments (**S**) ≤ 1000

1 ≤ length of a rope segment (**L**) ≤ 100

#### Small dataset

**N** ≤ 5

#### Large dataset

**N** ≤ 50

### Sample

Input | Output |

` 4` |
` Case #1: 0` |

### Solution

from sys import stdin f = open('output.out', 'w') for i in range(0, int(stdin.readline())): stdin.readline() segments = stdin.readline().split() blue = [] red = [] for j in segments: if j[len(j)-1] == 'B': blue.append(int(j[0:len(j)-1])) else: red.append(int(j[0:len(j)-1])) if len(blue) == 0 or len(red) == 0: print 'Case #'+str(i+1)+': 0' f.write('Case #'+str(i+1)+': 0\n') continue blue = sorted(blue, reverse = True) red = sorted(red, reverse = True) sum = 0 segUsed = 0 length = 0 if len(blue) > len(red): length = len(red) else : length = len(blue) for k in range(0, length): sum += blue[k] sum += red[k] segUsed += 2 print 'Case #'+str(i+1)+': ' + str(sum-segUsed) f.write('Case #'+str(i+1)+': ' + str(sum-segUsed)+'\n') f.close()

I have been absent for a while, but now I remember why I used to love this web site. Thank you, I will try and check back more often. How frequently you update your web site?