
ZOJ Problem Set  2569
Chief Judge of the Galactic Programming Contest in 3141�C3157 has recently published his memoirs in which he writes about sensational facts. The jury of the contest used to make problem sets specially designed for some teams to win. In the book the judge described the technics used in details. In this problem you are asked to implement the algorithm used by the judges. Before the contest the jury prepares m problems, each characterized with its intellectuality I_{i}, technics requirements A_{i}, code length L_{i}, and ordinariness O_{i}. The goal of the jury is to select n problems for the contest. Each team participating in the contest is in turn characterized by its theoretical background T_{j}, programming technics Z_{j}, typing speed V_{j}, and contests practice C_{j}. The jth team can solve ith problem if and only if T_{j} + C_{j} exceeds I_{i}  O_{i}. The team solves problems one after one, in the ascending order of expected solution time. Expected solution time for the problem is If the team does not finish to solve the problem within the contest length l, it does not solve it. If the team finished to solve problem exactly when the contest is over, we consider that it has solved the problem. The teams are finally arranged in the descending order by the number of problems solved, and if the number is equal, in the ascending order by the penalty time. The penalty time is the sum of penalties for each solved problem. The penalty time for the problem is the time from the beginning of the contest till the moment the problem is solved. Teams with equal both number of solved problems and penalty time have the same highest possible for them rank. The unsuccesful runs are ignored in the model, because it is difficult to predict them. Given the descriptions of m problems and t teams, select n such problems, that the team 1 gets the highest possible rank. Input The first line of the input file contains m, n, t and l (1 <= m <= 16, 1 <= n <= 12, n <= m, 1 <= t <= 20, 10 <= l <= 500). The following m lines describe problems, each line contains I_{i}, A_{i}, L_{i} and O_{i} (all numbers are integer, ranging from 1 to 1000, except L_{i} which is from 100 to 50 000). The following t lines describe teams, each line contains T_{j}, Z_{j} , V_{j} and C_{j} (all numbers are integer, ranging from 1 to 1000). Output Output n integer numbers in the ascending order  the problems that must be selected. Sample Input 3 2 4 60 20 40 2200 10 60 10 600 10 10 20 1500 40 100 10 100 10 100 30 70 2 20 20 300 10 30 1 100 1
Sample Output 2 3
Author: Andrew Stankevich Source: Andrew Stankevich's Contest #4 