업무 줄이기

책상 위에 서류 작업이 쌓이기 시작했고, 직장 내 긴장도 높아지고 있습니다. 상사는 오늘 안에 진전을 보이지 못하면 당신을 해고하겠다고 으름장을 놓았습니다. 현재 책상 위에는 $N$개의 서류 업무가 있으며, 상사는 하루가 끝날 때 정확히 $M$개의 서류 업무만 남아 있기를 요구합니다.

이제 유일한 희망은 도움을 고용하는 것입니다. 서류 업무를 줄여 주는 여러 대행사가 있으며, 각 대행사는 다음 두 가지 작업을 제공합니다.

• 비용 $A 를 내면 서류 업무를 1개 줄여 줍니다.
• 비용 $B 를 내면 현재 서류 업무 전체를 절반으로 줄여 줍니다(홀수일 때는 내림).

서류 업무는 절대 0개 미만으로 줄일 수 없습니다.

당신의 임무는 각 대행사 이름과 그 대행사를 이용해 문제를 해결하는 데 드는 최소 비용을 담은 정렬된 표를 출력하는 것입니다.

입력의 첫 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 하나 주어집니다. 각 테스트 케이스는 공백으로 구분된 세 개의 양의 정수 $N$, $M$, $L$로 시작합니다. $N$은 시작 업무량, $M$은 목표 업무량, $L$은 이용 가능한 대행사의 수이며 ($1 \le M \le N \le 100000$, $1 \le L \le 100$) 입니다. 이어지는 $L$개의 줄은 각각 이름:A,B 형식이며, $A$와 $B$는 위에서 설명한 해당 대행사의 요금입니다($0 \le A, B \le 10000$). 대행사 이름의 길이는 1자 이상 16자 이하이고 대문자 알파벳으로만 이루어지며, 서로 겹치지 않습니다.

각 테스트 케이스마다 먼저 Case X를 한 줄에 출력합니다. 여기서 $X$는 테스트 케이스 번호입니다. 그 뒤에 각 대행사 이름과 해당 대행사의 최소 비용을 최소 비용의 오름차순으로 정렬하여 출력합니다. 최소 비용이 같은 대행사들은 이름의 알파벳 순으로 정렬합니다. 표의 각 줄에는 대행사 이름, 공백, 그리고 그 대행사가 문제를 해결하는 데 필요한 최소 비용을 차례로 출력합니다.