Holiday Costing

Resort hotels often offer "stay/pay" deals: after you stay a certain number of nights, some of those nights become free. For example, in a stay 8 / pay 7 deal, staying 8 nights means you pay for only 7 (one night is free), and staying 9 nights means you pay for 8.

These deals can accumulate. For example, a stay 6 / pay 4 deal that may be repeated up to three times also creates an effective stay 12 / pay 8 deal and a stay 18 / pay 12 deal. A single hotel may offer several stay/pay deals, but different deals cannot be combined with one another.

Write a program that finds the best price for a given length of stay, choosing the single most advantageous deal (repeated when allowed) for that stay.

The input contains several data sets, one for each hotel.

The first line for a hotel is the hotel name: up to 20 characters, possibly including spaces.

Next come between 0 and 10 stay/pay deals, one per line. Each deal is three integers in the range 1 to 99: the stay length, the pay length, and how many times the deal may be repeated. The list of deals ends with a line 0 0 0.

After the deals comes a list of stay lengths, one integer per line, each in the range 1 to 99. This list ends with a line containing a single 0, which is not processed.

The whole sequence of hotels ends with a line containing a single #.

For every stay length in the input, print one line giving the minimum number of nights that must be paid for. This minimum is made up of standard nights (you pay for every night you stay) together with at most one stay/pay deal, repeated as many times as allowed when that helps.

Print each line in exactly this format:

Stay <n> nights at <name>, pay <p>.

where <n> is the number of nights stayed, <name> is the hotel name, and <p> is the minimum number of nights paid for. Use night (singular) when <n> is 1 and nights otherwise, matching the sample output.