The latest quarterly report of the Pump Organization does not look promising at all: the costs exploded while the revenue decreased by 42%. Taking a closer look at the numbers, CEO Dagobert J. Pump comes to the conclusion that the only way to save the company is to fire some of the employees.
The problem is that CEO Pump just recently claimed in an interview that "he is the greatest job creator that God ever created". So if he fired too many people, the dishonest corrupted left-wing media would certainly report about it, which would make him look extremely unreliable. The PR experts of the Pump Organization already estimated a number of employees that CEO Pump may fire without raising any attention in the media. To be on the safe side, CEO Pump further decides to fire as few employees as possible.
Taking a list of all employees of his company and their respective salary, CEO Pump has to save at least d Dollars by firing not more than k employees. If this is possible, CEO Pump wants to personally tell each and every one of them: YOU ARE FIRED!
The input consists of:
All si are distinct and only contain lowercase and uppercase letters of the English alphabet.
If there is no way to save at least d Dollars by firing not more than k employees, output impossible.
If there is a way to save at least d Dollars by firing not more than k employees, then the output consists of:
If there are multiple solutions, any of them will be accepted.
5 2000 3 John 999 Lyndon 450 Richard 1234 Gerald 1001 Jimmy 300
2 Richard, YOU ARE FIRED! Gerald, YOU ARE FIRED!
3 5555 2 Ronald 1000 George 2000 Bill 3000