Job Scheduling by Open Bidding

Your team is setting up a computing resource devoted to batch processing of compute-bound jobs. Scheduling is static within each period of time, so for every set of candidate jobs you have to find the mix that earns the most.

Jobs arrive through an open bid. A client states the amount of processor time to reserve, in seconds, and the dollar amount to pay for it. A job that finishes early still costs the client the full amount. A job that runs past its requested time is terminated, and the client still pays the full amount. For scheduling purposes, assume every job uses its entire slot.

In the interest of good customer relations, a bid stays out of the schedule when there is not enough time left to satisfy it. We are not going to over-book the way airlines do and then hope someone leaves part of the allotment unused.

So the task is this: choose bids whose requested times add up to at most the available time, and make the total payment as large as possible.

The first line holds a single integer, the number of problem sets in the file.

Each problem set takes n+2 lines.

• one integer n, the number of candidate jobs to be scheduled (n ≤ 500)
• n lines giving one bid each: an integer number of seconds, a single space, then a dollar amount in decimal form with exactly two digits to the right of the decimal point
• one integer t, the amount of time to be scheduled with these jobs (t ≤ 2000)

There is no white space beyond what is described above.

Print one line for each problem set, numbered beginning at one.

Problem <k>: <t> seconds scheduled for $abc.de

<k> is the problem set number and <t> is the total time actually scheduled, which may be less than the input time. The amount is the total payment for the scheduled bids, always written with the leading currency symbol and two digits to the right of the decimal point.

When several selections reach the same maximum payment, print the one whose total time is smallest.

There are no blank lines, and the final line ends with the new-line character.