There are n factories. Each factory can be assigned to produce one of the two kinds of cars (car A& car B). The net profit of producing car A or car B for each factory will be given. The goal is to assign x factories to produce car Aand y factories to produce car B so that the net profit is maximized. It is possible that some factories do not produce any cars (i.e. x + y <= n).
Suppose that you can choose two factories and switch the profits of car A for those two factories. You need to take into consideration of all possible switches and assignments of production, and find the best way to maximize the total profit. Based on the solution, your program needs to print the names of the x factories that produce car A in lexicographical order. If there are multiple answers, you need to print the one such that the total net profit of car Ai s maximum.
Note that if two factory produce same profits, choose the one with smaller lexicographical order. The swtich of car A of any two factory can be executed once only.
Note that when switch executed, the name of factory or the profit of car B will not be changed.
The first line contains four integers n, x, y, representing the total number of factories, the number of factories planned to produce car A, and the number of factories planned to produce car B.
Each of the next n lines contains one string si and two integers ai, bii, representing the name of each factory and the net profit each factory can make if it is assigned to produce car A or car B.
It is guaranteed that
Find the assignment of the car type for each factory so that the profit is maximized.
Print the list of x factories that need to produce car A in lexicographical order.