시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB9021100.000%

문제

색(빨간색, 노란색, 초록색, 파란색) 이 있는 타일에 숫자가 적혀있다. 타일의 정보는 다음과 같이 주어진다. 1r은 빨간색 타일에 1이 적힌 것을 의미하고, 3y는 노란색 타일에 3이 적힌 것을 의미한다. 즉, 앞에 있는 숫자는 타일에 적힌 숫자를 의미하고, 뒤에 있는 알파벳 소문자는 색을 의미한다. (r : 빨간색, y : 노란색, g : 초록색, b : 파란색)

이러한 타일을 가지고 게임을 하려 한다. 같은 색의 타일이고 연속된 숫자의 타일을 3개 이상 제거 시키면 그 연속된 숫자의 합만큼 점수를 얻게 된다. 예를 들면 9r, 10r, 11r 을 제거시키면 30점을 얻게 되고, 60g, 61g, 62g, 63g, 64g, 65g를 선택하면 374점의 점수를 얻게 된다. 그리고 같은 숫자이고 다른 색의 타일을 3개 이상 제거 시키면, 역시 그 타일들의 숫자의 합만큼 점수를 얻게 된다. 예를 들어 1r, 1g, 1b 를 제거 시키면 3점을, 17r, 17g, 17b, 17y를 제거시키면 68점을 얻게 된다.

이러한 규칙으로 타일을 제거 시킬 때, 최대한 점수를 많이 얻으려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오. (타일을 선택하면 제거시켜야 하므로 같은 타일을 두 번 더할 수는 없다.)

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

  • 첫째 줄에 타일의 개수 (1 ≤ N ≤ 400)이 주어진다.
  • 둘째 줄에 공백을 사이에 두고 N개의 타일의 정보가 주어진다. 각 타일에 있는 숫자는 1 이상 100 이하이며, 같은 타일은 들어오지 않는다.

출력

각 테스트 케이스마다 가능한 최대 점수를 한 줄에 하나씩 출력한다.

예제 입력 1

3
5
7g 7b 7r 8r 9r
7
23b 1y 24b 1r 93b 1b 100r
8
2y 2r 2g 2b 4g 5g 6g 7g

예제 출력 1

24
3
30
W3sicHJvYmxlbV9pZCI6IjIwNTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzBcdWM3N2MgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzkoXHViZTY4XHVhYzA0XHVjMGM5LCBcdWIxNzhcdWI3ODBcdWMwYzksIFx1Y2QwOFx1Yjg1ZFx1YzBjOSwgXHVkMzBjXHViNzgwXHVjMGM5KSBcdWM3NzQgXHVjNzg4XHViMjk0IFx1ZDBjMFx1Yzc3Y1x1YzVkMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LiBcdWQwYzBcdWM3N2NcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAxclx1Yzc0MCBcdWJlNjhcdWFjMDRcdWMwYzkgXHVkMGMwXHVjNzdjXHVjNWQwIDFcdWM3NzQgXHVjODAxXHVkNzhjIFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIDN5XHViMjk0IFx1YjE3OFx1Yjc4MFx1YzBjOSBcdWQwYzBcdWM3N2NcdWM1ZDAgM1x1Yzc3NCBcdWM4MDFcdWQ3OGMgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQwYzBcdWM3N2NcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIFx1YjRhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjI5NCBcdWMwYzlcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiAociA6IFx1YmU2OFx1YWMwNFx1YzBjOSwgeSA6IFx1YjE3OFx1Yjc4MFx1YzBjOSwgZyA6IFx1Y2QwOFx1Yjg1ZFx1YzBjOSwgYiA6IFx1ZDMwY1x1Yjc4MFx1YzBjOSk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1ZDBjMFx1Yzc3Y1x1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWMwYzlcdWM3NTggXHVkMGMwXHVjNzdjXHVjNzc0XHVhY2UwIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWMyMmJcdWM3OTBcdWM3NTggXHVkMGMwXHVjNzdjXHVjNzQ0IDNcdWFjMWMgXHVjNzc0XHVjMGMxIFx1YzgxY1x1YWM3MCBcdWMyZGNcdWQwYTRcdWJhNzQgXHVhZGY4IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHViOWNjXHVkMDdjIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0IDlyLCAxMHIsIDExciBcdWM3NDQgXHVjODFjXHVhYzcwXHVjMmRjXHVkMGE0XHViYTc0IDMwXHVjODEwXHVjNzQ0IFx1YzViYlx1YWM4YyBcdWI0MThcdWFjZTAsIDYwZywgNjFnLCA2MmcsIDYzZywgNjRnLCA2NWdcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViYTc0IDM3NFx1YzgxMFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWM3NzRcdWFjZTAgXHViMmU0XHViOTc4IFx1YzBjOVx1Yzc1OCBcdWQwYzBcdWM3N2NcdWM3NDQgM1x1YWMxYyBcdWM3NzRcdWMwYzEgXHVjODFjXHVhYzcwIFx1YzJkY1x1ZDBhNFx1YmE3NCwgXHVjNWVkXHVjMmRjIFx1YWRmOCBcdWQwYzBcdWM3N2NcdWI0ZTRcdWM3NTggXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1YjljY1x1ZDA3YyBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCAxciwgMWcsIDFiIFx1Yjk3YyBcdWM4MWNcdWFjNzAgXHVjMmRjXHVkMGE0XHViYTc0IDNcdWM4MTBcdWM3NDQsIDE3ciwgMTdnLCAxN2IsIDE3eVx1Yjk3YyBcdWM4MWNcdWFjNzBcdWMyZGNcdWQwYTRcdWJhNzQgNjhcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YWRkY1x1Y2U1OVx1YzczY1x1Yjg1YyBcdWQwYzBcdWM3N2NcdWM3NDQgXHVjODFjXHVhYzcwIFx1YzJkY1x1ZDBhYyBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWM4MTBcdWMyMThcdWI5N2MgXHViOWNlXHVjNzc0IFx1YzViYlx1YzczY1x1YjgyNFx1YmE3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gKFx1ZDBjMFx1Yzc3Y1x1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgXHVjODFjXHVhYzcwXHVjMmRjXHVjZjFjXHVjNTdjIFx1ZDU1OFx1YmJjMFx1Yjg1YyBcdWFjMTlcdWM3NDAgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YjQ1MCBcdWJjODggXHViMzU0XHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFjMWNcdWMyMTggKDEgJmxlOyBOICZsZTsgNDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgTlx1YWMxY1x1Yzc1OCBcdWQwYzBcdWM3N2NcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDBjMFx1Yzc3Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IDEgXHVjNzc0XHVjMGMxIDEwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWJhNzAsIFx1YWMxOVx1Yzc0MCBcdWQwYzBcdWM3N2NcdWM3NDAgXHViNGU0XHVjNWI0XHVjNjI0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDUwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUnVtbWlrdWIiLCJkZXNjcmlwdGlvbiI6IjxwPlJ1bW1pa3ViIGlzIGEgc2ltcGxlIGdhbWUsIG9mdGVuIHBsYXllZCBieSBlbGRlcmx5IHBlb3BsZSB2ZXJzdXMgdGhlaXIgZ3JhbmRjaGlsZHJlbi4gSXQgaXMgYSB0aWxlLWJhc2VkIGdhbWUgYW5kIGVhY2ggb2YgdGhlIHRpbGVzIGhhcyBhIGNvbG9yZWQgbnVtYmVyIHdyaXR0ZW4gb24gaXQuIFRoZXJlIGFyZSBmb3VyIGF2YWlsYWJsZSBjb2xvcnM6IHllbGxvdywgcmVkLCBncmVlbiBhbmQgYmxhY2suIEEgdGlsZSBpcyBkZXNjcmliZWQgYnkgaXRzIG51bWJlciBmb2xsb3dlZCBieSBhIGxvd2VyIGNhc2UgbGV0dGVyLCB3aGljaCBpcyB0aGUgZmlyc3QgbGV0dGVyIG9mIGl0cyBjb2xvci4gQWxsIHRpbGVzIGFyZSB1bmlxdWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBnb2FsIG9mIGdhbWUgaXMgc2ltcGxlOiBnZXQgcmlkIG9mIGFsbCB5b3VyIHRpbGVzLiBUaGlzIHNvdW5kcyBlYXNpZXIgdGhhbiBpdCBpcywgc2luY2UgeW91IGNhbiBvbmx5IHVzZSB0aGVtIGluIHR3byBzcGVjaWZpYyB3YXlzLiBZb3UgY2FuIGdldCByaWQgb2YgdGlsZXMgYnkgY29uc3RydWN0aW5nIHJ1bnMgb3IgZ3JvdXBzLiBBIHJ1biBpcyBjb21wb3NlZCBvZiB0aHJlZSBvciBtb3JlIGNvbnNlY3V0aXZlIG51bWJlcnMgb2YgdGhlIHNhbWUgY29sb3IsIGZvciBleGFtcGxlIDlyLCAxMHIsIDExciwgb3IgNmcsIDYxZywgNjJnLCA2M2csIDY0ZywgNjVnLiBBIGdyb3VwIGlzIGNvbXBvc2VkIG9mIHRocmVlIG9yIGZvdXIgdGlsZXMgd2l0aCB0aGUgc2FtZSBudW1iZXJzLCBhbmQgdGhlcmVmb3JlIGRpZmZlcmVudCBjb2xvcnMuIEV4YW1wbGVzIGFyZSAxciwgMWcsIDFiIGFuZCAxN3IsIDE3ZywgMTdiLCAxN3kuIEluIGNvbnN0cnVjdGluZyB0aGUgcnVucyBhbmQgZ3JvdXBzLCB5b3UgbWF5IG9ubHkgdXNlIGVhY2ggdGlsZSBvbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdmFsdWUgb2YgYSBydW4gb3IgZ3JvdXAgaXMgdGhlIHN1bSBvZiB0aGUgbnVtYmVycyBvbiB0aGUgdGlsZXMuIFlvdXIgc2NvcmUgaXMgdGhlIHN1bSBvZiB0aGUgdmFsdWVzIG9mIGFsbCB0aGUgcnVucyBhbmQgZ3JvdXBzIHlvdSBjb25zdHJ1Y3QuIFdoYXQgaXMgeW91ciBtYXhpbXVtIHBvc3NpYmxlIHNjb3JlPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2UgaGFzIHRoZSBmb2xsb3dpbmcgZm9ybWF0OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggb25lIGludGVnZXIgTiwgc2F0aXNmeWluZyAxICZsZTsgTiAmbGU7IDQwMDogdGhlIG51bWJlciBvZiB0aWxlcyB5b3UgaGF2ZS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBOIHN0cmluZ3Mgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMsIGVhY2ggY29uc2lzdGluZyBvZiBhIG51bWJlciBiZXR3ZWVuIDEgYW5kIDEwMCBhbmQgYSBjaGFyYWN0ZXIgd2hpY2ggaXMgZWl0aGVyICYjMzk7eSYjMzk7LCAmIzM5O3ImIzM5OywgJiMzOTtnJiMzOTssICYjMzk7YiYjMzk7OiB0aGUgYXZhaWxhYmxlIHRpbGVzLiBBbGwgdGlsZXMgYXJlIHVuaXF1ZS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgaW4gdGhlIGlucHV0LCB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIG51bWJlciwgb24gYSBzaW5nbGUgbGluZTogdGhlIG1heGltdW0gcG9zc2libGUgc2NvcmUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==