문제
Rummikub는 간단한 퍼즐 게임이다. Rummikub에서는 타일을 이용해서 게임을 진행하며,
각각의 타일들은 색이 칠해진 숫자를 가지고 있다.
• 색깔은 4가지 종류가 있다 : Red, Green, Black, Yellow (rgby) • 타일은 각 색깔의 첫 번째 글자 (r, g, b, y) 와 숫자로 표현된다. • 모든 타일은 유일하다. 즉 색과 숫자가 같은 타일은 존재 할 수 없다.
게임의 목적은 간단하다 : 타일들을 제거하는 것이다.
이것은 쉽게 들릴지도 모르지만, 당신은 제거할 때 오직 2가지 방법만 사용해야 한다.
당신은 타일들을 run와 group 묶음을 만들어버림으로써 제거할 수 있다.
run이란, 3개 이상의 연속된 숫자와, 같은 색으로 이루어진 타일 무리를 말한다. 예를 들어서 9r, 10r, 11r을 run이라 할 수 있고 60g, 61g, 62g, 63g, 64g, 65g를 run이라 할 수 있다.
group이란, 같은 숫자로 이루어진 3개 또는 4개의 타일 무리를 말한다. 예를 들어서, 1r 1g 1b는 group이고, 17r, 17b, 17g, 17y 또한 group이다.
참고로, 한 번 제거된 타일은 두 번 다시 제거될 수 없다.
run과 group의 점수는 타일들에게 주어진 숫자들의 합이다.
당신의 점수는 당신이 만들어서 제거한 run과 group의 각 타일들이 가진 숫자들의 합이다.
당신의 최대 점수는 얼마인가?
입력
첫 번째 줄에는 테스트 테이터의 개수 T(1≤T≤10)가 주어진다. 그 다음 줄부터 테스트 데이터 T개가 주어지는데, 각 테스트데이터의 첫째 줄에는 타일의 개수 N(1≤N≤400)이 주어지며, 그 다음 줄에는 N개의 타일 정보가 입력된다.
각 테스트데이터의 첫째 줄에는 정수 N이 주어진다. 이는 타일의 개수로, 1 이상 400 이하의 자연수이다. 그 다음 줄에는 N개의 타일의 정보가 공백으로 구분되어 주어진다. 타일의 정보는 문자열로 이루어져 있으며 앞쪽에 1이상 100이하의 숫자, 뒤쪽에 r, g, b, y 네개의 문자 중 하나의 형식으로 입력된다.
출력
각각의 테스트 데이터에 대해서 최대 점수를 출력한다.
예제
3
5
7g 7b 7r 8r 9r
7
23b 1y 24b 1r 93b 1b 100r
8
2y 2r 2g 2b 4g 5g 6g 7g
24
3
30
로그인해야 코드를 작성할 수 있어요.