시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 1 1 33.333%

문제

Resort hotels often offer "stay/pay" deals where after so many nights you get some nights free. For example, in a stay 8 / pay 7 deal, if you stay 8 nights then you only pay for 7 (one is free). If you stay 9 then you pay for 8. Often these deals can accumulate. For example, a stay 6 pay 4 deal that can be repeated three times means that stay 12 pay 8 and stay 18 pay 12 deals also exist. Some hotels offer multiple stay pay deals, however these cannot be combined.

Write a program that will calculate the best rate for a given stay, i.e. that will choose the best (possibly repeated) deal for a given length of stay.

입력

Input consists of a number of sets of data, each relating to one hotel. The first line for each hotel is the name of the hotel, a sequence of up to 20 characters, possibly including spaces. This is followed by between 0 and 10 lines of stay/pay deals. Each stay/pay deal consists of three integers in the range 1 to 99: stay, pay, number of repeats. The stay/pay section is terminated by a line consisting of three zeroes (0 0 0). Following the stay/pay section is a series of integers, one per line, indicating some number of nights (also in the range 1 to 99), terminated by a line containing a single 0. This line should not be processed. The sequence of hotels is terminated by a line consisting of a single #.

출력

Output consists of one line for each number of nights in the input, indicating the minimum number of nights that have to be paid for. Note that this minimum must be made up of a combination of standard deals (pay for as many nights as you stay) and at most one stay/pay deal, repeated if necessary. Match the sample output format given below.

예제 입력 1

Hotel xyz
8 7 3
10 8 1
0 0 0
1
12
23
24
0
Hotel abc
0 0 0
11
0
#

예제 출력 1

Stay 1 night at Hotel xyz, pay 1.
Stay 12 nights at Hotel xyz, pay 10.
Stay 23 nights at Hotel xyz, pay 21.
Stay 24 nights at Hotel xyz, pay 21.
Stay 11 nights at Hotel abc, pay 11.