Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2569
Unfair Contest

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

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

But the actual time required to solve the problem is
If two problems have the same expected solution time, we consider the team lucky, and suggest that if first solves the problem with smaller actual required time.

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.

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
Submit    Status