In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of January 4th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #12 exercise sheet]
(this problem is an adaptation from an ONI'2007 national final problem)
Space tourism started in April 2001, when American businessman Dennis Tito became the first ever space tourist to travel to space aboard a Soyuz russian spacecraft. During the period from 2001 to 2009, seven space tourists made flights aboard Soyuz spacecrafts to International Space Station. The publicized price was in the range of 20 to 25 million dollars per trip.
Working at PAST (Portuguese Agency for Space Tourism), you're tasked with helping to do some market research. PAST is about to complete a small spacecraft capable of carrying just one space tourist, and they want to maximise their profit. The strategy they want to implement is very simple: when a client wants to travel, they tell PAST how much they are willing to pay per day in space and how many days they want. When the spacecraft is on Earth, PAST chooses the customer who pays the most per day of stay (if there are several customers paying the same maximum amount, the one who placed the order earliest should be chosen). After travelling for the requested time, the spacecraft returns to Earth and again chooses the customer who pays the most per day, and so on until everyone has been served. If, when the spacecraft arrives back on Earth, there are no customers to serve, it waits for someone's request to come in and serves them immediately.
PAST wants to see if this strategy works, and is very interested to know how long each customer waits on our planet before being served.
To better understand how the strategy works, take a look at this example:
| Client Name | Money it pays (millions of dollars) |
Travel time (days, includes going and returning) |
Time at which the request arrived (days) |
|---|---|---|---|
| Musk | 100 | 20 | 5 |
| Bezos | 300 | 10 | 10 |
| Zuckerberg | 500 | 99 | 17 |
Imagine that the spacecraft starts operating on the day 6. At that time only Musk's order exists (it arrived on day 5). So Musk left with a waiting time of 1 day. The spacecraft takes him and takes 20 days to return, arriving on the 26th. By then, PAST already has Bezos' and Zuckerberg's orders in hand. It's Zuckerberg who pays more, so the spacecraft takes him, making him wait precisely 9 days. The journey takes 99 days and the spacecraft returns precisely on day 125 to serve Bezos, who has been waiting 115 days.
Your task is to simulate the desired operating strategy and for a set of given orders, computing out how long each customer is waiting to be served, taking into account the day the order arrived, how much money per day they were willing to pay and how long the journey was.
The first line of input contains an integer S, indicating the day on which PAST starts operating the spacecraft.
This is followed by a line with a single integer N, indicating the number of customers to be served.
This is followed by N lines describing the customer offers, already sorted in increasing order of order of arrival (no two customer requests arrive on the same day). Each line has the following format: "NAME MONEY DURATION ARRIVAL_TIME"
The output consists of N lines, one for each customer, describing how long each customer has waited to be served, in the format "NAME MONEY WAITING_TIME" (WAITING_TIME is an integer that tells you how many days the customer has waited).
The list of customers should be sorted in descending order of the money paid per day (PAST is greedy and wants to know how long the best customers wait first). If there are several customers paying the same amount, the customer who arrived earliest should appear first in the output.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ S ≤ 500 000 | Day the spacecraft starts to operate | |
| 1 ≤ N ≤ 50 000 | Number of clients | |
| 1 ≤ |NAME| ≤ 10 | Length of each client name | |
| 1 ≤ MONEY ≤ 5 000 | Money each client offers to pay | |
| 1 ≤ DURATION ≤ 100 | Duration of each client journey | |
| 1 ≤ ARRIVAL_TIME ≤ 500 000 | Day of arrival of a client order |
| Example Input 1 | Example Output 1 |
6 3 Musk 100 20 5 Bezos 300 10 10 Zuckerberg 500 99 17 |
Zuckerberg 500 9 Bezos 300 115 Musk 100 1 |
Explanation of Example Input 1
The example input is explained in the problem statement.
| Example Input 2 | Example Output 2 |
1 4 Manuel 200 3 3 Joaquim 100 3 4 Maria 150 3 5 Conceicao 250 3 6 |
Conceicao 250 0 Manuel 200 0 Maria 150 4 Joaquim 100 8 |