F :: Auctions
Time Limit: 2 Seconds Memory Limit: 65536 KB
An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the good to the highest bidder. Precisely, first a minimum price is set for an item, then bidders propose their bids. At the auction end time of the item, it is sold to the bidder who proposed the maximum bid. You are to write a program that tracks auctions for several items and output the results.
Input
Input consists of three sections namely items, bidders and bids coming respectively in the input.
Item section: The first line of the item section contains a single number k < 100 denoting the number of items. Each next k lines contain item id, its minimum price and its auction end time. Item id is a non-negative integer number, and minimum price is a non-negative real number, and auction end time is in the 24-hour format of XX:YY:ZZ where XX is in hours from 00 to 23, YY is in minutes from 00 to 59, and ZZ is in seconds from 00 to 59. Note a bid for an item is acceptable if it is proposed not later than the auction end time of the item and the proposed price is not less than the minimum price of the item.
Bidder section: This section starts with a line containing a single number m < 100 which is the number of bidders. Each next m lines contains bidder id and its balance account separated by spaces. Bidder id is a non-negative integer number, and balance account is a non-negative real number. Note that a bidder can propose a price larger than its account balance but at the auction end time this bid is considered as an invalid bid and is not taken into account. At the auction end time of an item, the account balance of the winner is deducted by her/his bid amount for that item.
Bid section: This section also starts with a line containing a single number n < 100, the number of bids. Each next n lines contains item id, bidder id, bid amount and bid time all separated with spaces. This means given bidder proposes the given bid amount at the given bid time for the given item. Their formats are as described above. Recall that a bidder can buy a item (win the auction for the item) if he propose a bid not later than the auction end time of the item and his bid amount is not less than the minimum price of the item and moreover his bid is highest among all valid bids for the item. Note that at the auction end time of the item, the winner is specified and the account-balance of the winner is updated.
You are guaranteed that no two items have the same auction end time and no two bids have the same bid time and bid amount. Note that bidder ids and item ids are unique but a bidder id can be equal to an item id and you may assume all ids in the input are valid.
Output
Output one line for each item being auctioned, in order of their auction end time, printing "Item <item id> Bidder <bidder id> Price <winning bid amount>". Note there should be a space between any two words in the output. If there is not a winning bid for an item, print "Item <item id> is not sold". Price in the output must be printed with exactly 2 digits after the decimal point.
Sample Input
2 1 10.00 04:27:31 5 31.00 19:25:44 2 13 41.33 95 77.77 3 1 13 60.00 02:26:32 5 13 41.21 04:45:21 5 95 51.00 08:43:25
Sample Output
Item 1 is not sold Item 5 Bidder 95 Price 51.00Submit
Source: 10th Iran Nationwide Internet Contest