논쟁 피하기

해적 선장과 선원들은 보석이 가득 찬 상자를 보고 기뻐했다. 다이아몬드, 루비, 사파이어, 오팔 등 여러 종류의 보석이 반짝이는 컬렉션을 채우고 있었다.

"우리는 부자다, 얘들아!" 선장이 말했다. "자, 이제 할 일을 정하겠다. 지금은 각자 돌을 두 개씩 가져간다. 나머지는 묻어 둘 거다. 원래 해적이 그렇게 하니까! 또한 모두 서로 다른 종류의 보석을 두 개 가져가야 한다. 다음 항구에서 상인들이 무엇을 살지 모르니, 다음 항구 근처에 루비 광산이 번창해도 루비만 가져간 놈의 불평은 듣고 싶지 않다."

"누가 먼저 고릅니까?" 답을 이미 아는 것 같아 불안해진 사환 소년이 물었다.

"내가 먼저 하나를 고른다." 선장이 말했다. "그다음은 일등항해사부터 사환까지 계급 순서대로 한 명씩 고른다." 계급이 낮은 선원들이 투덜거리기 시작했다. 선장이 말을 이었다. "그다음 사환이 바로 두 번째 보석을 고른다. 그 뒤로는 역순으로 진행해서 마지막으로 내가 두 번째 돌을 고른다."

선원들은 곧 동의했고, 거의 동시에 이 방식에서 가장 좋은 돌을 차지할 방법을 생각하기 시작했다.

다른 선원들이 어떻게 고르든 자신이 확실히 얻을 수 있는 보석 가치의 합이 최대가 되도록, 선원이 처음에 어떤 돌을 골라야 하는지 알아내는 프로그램을 작성하라.

입력은 하나 이상의 데이터 세트로 구성된다.

각 데이터 세트는 정수 두 개 $M$, $N$이 적힌 줄로 시작한다. $M$은 사용 가능한 보석 종류의 수이고, $N$은 당신 다음에 첫 번째 돌을 고르고 당신 전에 두 번째 돌을 고르는 선원의 수이다. 각 데이터 세트에서 $2 \leq M \leq 26$, $0 \leq N \leq 10$이다. $M$이 0이면 입력이 끝났음을 뜻한다.

데이터 세트의 나머지는 $M$개의 줄로 이루어지며, 각 줄은 사용 가능한 보석 종류 하나를 설명한다. 각 줄은 보석 종류를 나타내는 대문자 알파벳 하나로 시작한다(예를 들어 'D'는 다이아몬드, 'Z'는 지르콘을 뜻할 수 있다). 같은 코드를 가진 종류는 없으며, 코드는 어떤 순서로든 나올 수 있다. 알파벳 코드 뒤에는 $N+1$개의 정수가 이어지며, 각각 그 종류에서 남은 가장 가치 있는 보석 $N+1$개 중 하나의 가치(더블룬)를 나타낸다. 이 값들은 가치의 비증가 순서로 주어진다. 값의 범위는 $0 \ldots 10\,000$이다.

각 데이터 세트마다 한 줄에 첫 번째로 골라야 할 보석 종류의 알파벳 코드를 출력한다. 이 보석은 나머지 선원들이 어떻게 고르든 두 번의 선택으로 확실히 받을 수 있는 합계 가치를 최대로 만드는 종류다. 최대 합계 가치가 같은 종류가 여럿이면 알파벳 순서상 가장 앞선 것을 출력한다.