cho.sh

고리 잇기 (Large)

빨간색과 파란색 조각을 같은 개수씩 골라 매듭 손실을 뺀 고리 전체 길이가 가장 길어지도록 합니다.

보통5그리디정렬면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

밧줄 조각이 가득 든 자루가 있다. 자루에는 조각이 S개 들어 있고, 각 조각은 파란색(B)이거나 빨간색(R)이며 길이가 센티미터 단위로 주어진다.

조각을 매듭으로 이어 닫힌 고리 하나를 만든다. 고리를 따라 색이 번갈아 나와야 하므로, 매듭으로 이어지는 두 조각의 색은 항상 서로 다르다. 이 조건 때문에 자루에 남는 조각이 생기기도 한다.

매듭 하나는 고리의 전체 길이를 1센티미터 줄인다. 매듭이 잇는 두 조각에서 0.5센티미터씩 가져가기 때문이다. 조각 m개로 만든 고리에는 매듭도 m개 있다.

자루에 든 조각의 색이 한 가지뿐이면 매듭을 하나도 지을 수 없고, 답은 0이다.

길이가 1인 조각을 쓰면 양쪽 매듭이 그 길이를 모두 가져가서 고리에 더해지는 길이가 0이 된다. 이렇게 써도 되며, 그 조각은 사용한 것으로 센다.

만들 수 있는 고리의 최대 길이를 구하라.

입력

첫째 줄에 테스트 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어지고, 각 테스트 케이스는 두 줄로 이루어진다.

  • 첫째 줄에 자루에 든 밧줄 조각의 수 S가 주어진다.
  • 둘째 줄에 값 S개가 공백으로 구분되어 주어진다. 각 값은 센티미터 단위 길이 L 뒤에 색을 나타내는 문자 B 또는 R이 바로 붙은 형태이다.

제한

  • 1 ≤ N ≤ 50
  • 1 ≤ S ≤ 1000
  • 1 ≤ L ≤ 100

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 만들 수 있는 고리의 최대 길이이다.