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 Ii, technics requirements Ai, code length Li, and ordinariness Oi. 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 Tj, programming technics Zj, typing speed Vj, and contests practice Cj.
The j-th team can solve i-th problem if and only if Tj + Cj exceeds Ii - Oi. 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.
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 Ii, Ai, Li and Oi (all numbers are integer, ranging from 1 to 1000, except Li which is from 100 to 50 000).
The following t lines describe teams, each line contains Tj, Zj , Vj and Cj (all numbers are integer, ranging from 1 to 1000).
Output n integer numbers in the ascending order - the problems that must be selected.
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
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4