Hotel

A tourism board has compiled a list of the room types available at every hotel in the city. Each record on the list contains:

1. Hotel name (at most 25 characters, letters only).
2. Bed size (20 - 62).
3. Room capacity (1 - 4).
4. Number of available rooms (1 - 50).
5. Cost per room (1 - 5,000).

To keep things simple, assume that every hotel offers exactly one room type, so each hotel appears on the list only once.

Several teams have submitted their hotel preferences, each consisting of:

• A preferred bed size, grouped into three categories:
  • Type A: bed size 20 - 35
  • Type B: bed size 36 - 48
  • Type C: bed size 49 - 62
• The number of people on the team (1 - 200).
• The maximum number of people allowed in a single room (1 - 4). Each room holds at most this many people, even if the room's capacity is larger.

For each team, find the cheapest hotel whose bed size falls in the team's preferred category and that has enough rooms to house everyone. Each room holds at most the smaller of (the room capacity) and (the team's per-room limit), so the team needs that many people divided into the number of people, rounded up, worth of rooms; the total cost is (rooms needed) times (cost per room).

If several hotels are equally cheap, choose the one with the largest bed size. If there is still a tie, choose the one that appears first on the list.

You do not need to worry about two teams being assigned to the same hotel - you are only making a suggestion for each team, not a reservation.

The first line contains an integer $T$, the number of test cases.

Each test case begins with a line containing two integers $N$ ($1 \le N \le 50$) and $M$ ($1 \le M \le 50$): the number of hotels and the number of teams. The next $N$ lines each describe one hotel with four integers - bed size, room capacity, number of available rooms, and cost per room - followed by a string, the hotel's name. The next $M$ lines each describe one team with three values: the bed-size type (A, B, or C), the number of people on the team, and the maximum number of people per room.

For each test case, first print Case #X: where $X$ is the test-case number (starting from 1). Then, for each team in the order they appear in the input, print a single line containing the total cost and the name of the suggested hotel, separated by one space. If no hotel matches a team's criteria, print no-hotel instead.