Hotel

Beijing Warmup Contest

Time Limit : 3 Second

Memory Limit : 128 MB

Submission: 144

Solved: 39

Description

Indonesia tourism board has just sent a list of available room type of all hotels in Jakarta for teams that will participate in Indonesia Programming Contest 2008. Each record on the list contains:

Hotel name (max. 25 char, alphabet only).

Bed size (20 - 62).

Room capacity (1 - 4).

Number of available room (1 - 50).

Cost per room (1 - 5,000).

To simplify the problem, let's assume that each hotel will offer only one type of room (which means they will appear only once in the list).

Several participants have submitted their hotel preference to the committee, which consists of:

Prefered bed size, grouped into three categories:

Type A: bed size 20 - 35

Type B: bed size 36 - 48

Type C: bed size 49 - 62

Number of people in their teams (1 - 200).

Maximum number of person in a room (1 - 4). The number of people in each room will be limited to this number even if the room has more capacity.

Based on the data above, write a program to find the cheapest hotel for each team. If there're more than one cheapest hotels, then choose one with largest bed size. If there're still more than one, then choose one which come first on the list.

You don't have to worry about multiple teams assigned at one hotel. What we will do here is only make a suggestion for each team, not a reservation.

Input

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

Each case will begin with two integers N (1 <= N <= 50) and M (1 <= M <= 50) the number of available hotel and the number of teams respectively. The next N lines each will contains four integers (bed size, room capacity, number of available room and the price per room) and a string which denotes the hotel's name. The next M lines each will contains three data: bed size type (A, B or C), number of people in their teams and maximum number of person in a room.

Output

Print "Case #X:" (X is the case number) at the first line of each test case. For each team, print on a single line the total cost and the hotel name which you suggested (in the same order as the team appearance in the input), separated by a single space. If there're no hotels that match the team's criteria, then output "no-hotel" (without quotes).

sample input

2
2 3
40 3 2 10 MyHotel
37 4 5 50 HisHotel
B 5 3
A 3 4
B 7 2
4 2
30 2 5 10 IndigoHotel
35 2 5 10 PurpleHotel
36 2 5 10 GreenHotel
36 2 5 10 BrownHotel
A 6 2
B 6 2

sample output

Case #1:
20 MyHotel
no-hotel
200 HisHotel
Case #2:
30 PurpleHotel
30 GreenHotel

hint

source

Submit