There are n factories. Each factory can be assigned to produce one of the three kinds of cars (car A, car B, & car C). The goal is to assign x factories to produce car A, y factories to produce car B, and z factories to produce car C so that the net profit is maximized. It is possible that some factories do not produce any cars (i.e. x + y + z <= n). Note that z can only be 1.
The net profit of producing car A, car B, or car C for each factory will be given. 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 A is maximum.
The first line contains four integers n, x, y, z, representing the total number of factories, the number of factories planned to produce car A, the number of factories planned to produce car B, and the number of factories planned to produce car C.
Each of the next n lines contains one string si and three integers ai, bi, ci, 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 or car C.
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.