Tiered Storage Bill

The story

Your startup keeps its backups in a cloud object store. The provider does not charge one flat price per gigabyte: it uses graduated tiers. The first gigabytes of a month are cheap (or free), the next block costs a different price, and so on. Every gigabyte is priced by the tier it falls into, not by the total you store.

The finance team wants a script that turns a rate card and a list of customers into a monthly bill.

The task

Read a rate card and a list of customers, and print the bill of every customer.

Input (whitespace-separated, read all of stdin):

1. T, the number of tiers.
2. T lines limit price. limit is the cumulative upper bound of the tier in GB (the first tier covers 0 .. limit, the next one previous limit .. limit). The last tier has the limit inf. price is USD per GB inside that tier.
3. N, the number of customers.
4. N lines name gb. name has no spaces, gb is the stored amount and may be fractional.

Output: one line per customer, in input order: name cost, where cost is the total in USD rounded to two decimals. The checker compares the numbers with a tolerance of half a cent.

A customer with 0 GB pays 0.00. Usage that lands exactly on a limit belongs to the tier that ends there.

Example

3
100 0.00
1000 0.023
inf 0.021
2
alice 50
bob 1500.5

Output:

alice 0.00
bob 31.21

alice stays inside the free first 100 GB. bob pays 0 for his first 100 GB, then 900 GB x 0.023 = 20.70, then the remaining 500.5 GB x 0.021 = 10.5105, a total of 31.2105.

3
100 0.00
1000 0.023
inf 0.021
2
alice 50
bob 1500.5