호텔

관광청이 도시의 모든 호텔에서 제공하는 객실 종류 목록을 정리했다. 목록의 각 항목은 다음 정보를 담고 있다.

1. 호텔 이름 (최대 25자, 영문자만 사용).
2. 침대 크기 (20 - 62).
3. 객실 정원 (1 - 4).
4. 이용 가능한 객실 수 (1 - 50).
5. 객실 1개당 요금 (1 - 5,000).

문제를 단순하게 하기 위해, 각 호텔은 한 가지 종류의 객실만 제공한다고 가정한다. 즉, 각 호텔은 목록에 한 번만 등장한다.

여러 팀이 각자의 호텔 선호 조건을 제출했으며, 각 조건은 다음으로 이루어진다.

• 선호하는 침대 크기. 세 가지 등급으로 나뉜다.
  • A 등급: 침대 크기 20 - 35
  • B 등급: 침대 크기 36 - 48
  • C 등급: 침대 크기 49 - 62
• 팀의 인원 수 (1 - 200).
• 한 객실에 배정할 수 있는 최대 인원 (1 - 4). 객실 정원이 이보다 크더라도 한 객실에는 이 인원까지만 배정한다.

각 팀에 대해, 침대 크기가 팀이 선호하는 등급에 속하면서 모든 인원을 수용할 수 있는 가장 저렴한 호텔을 찾아라. 한 객실에는 (객실 정원)과 (팀의 객실당 최대 인원) 중 더 작은 값만큼의 인원이 들어가므로, 팀은 (인원 수) ÷ (그 값)을 올림한 만큼의 객실이 필요하고, 총 요금은 (필요한 객실 수) × (객실 1개당 요금)이다.

가장 저렴한 호텔이 여러 개라면 침대 크기가 가장 큰 호텔을 택한다. 그래도 여러 개라면 목록에서 먼저 등장한 호텔을 택한다.

한 호텔에 여러 팀이 배정되는 경우는 신경 쓸 필요가 없다. 여기서는 각 팀에게 추천만 할 뿐, 실제 예약을 하는 것은 아니다.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 두 정수 $N$ ($1 \le N \le 50$)과 $M$ ($1 \le M \le 50$)이 주어지는 줄로 시작하며, 각각 호텔의 수와 팀의 수이다. 이어지는 $N$개의 줄에는 각각 한 호텔의 정보가 네 정수 - 침대 크기, 객실 정원, 이용 가능한 객실 수, 객실 1개당 요금 - 와 호텔 이름을 나타내는 문자열로 주어진다. 그다음 $M$개의 줄에는 각각 한 팀의 정보가 세 값 - 침대 크기 등급(A, B 또는 C), 팀의 인원 수, 한 객실당 최대 인원 - 으로 주어진다.

각 테스트 케이스에 대해 먼저 Case #X:를 출력한다. 여기서 $X$는 테스트 케이스 번호이며 1부터 시작한다. 그다음, 입력에 등장한 순서대로 각 팀에 대해 총 요금과 추천 호텔의 이름을 한 칸 띄어 한 줄에 출력한다. 팀의 조건에 맞는 호텔이 없으면 대신 no-hotel을 출력한다.