{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eChief 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.\u003c/p\u003e\n\u003cp\u003eBefore the contest the jury prepares m problems, each characterized with its intellectuality I\u003csub\u003ei\u003c/sub\u003e, technics requirements A\u003csub\u003ei\u003c/sub\u003e, code length L\u003csub\u003ei\u003c/sub\u003e, and ordinariness O\u003csub\u003ei\u003c/sub\u003e. The goal of the jury is to select n problems for the contest.\u003c/p\u003e\n\u003cp\u003eEach team participating in the contest is in turn characterized by its theoretical background T\u003csub\u003ej\u003c/sub\u003e, programming technics Z\u003csub\u003ej\u003c/sub\u003e, typing speed V\u003csub\u003ej\u003c/sub\u003e, and contests practice C\u003csub\u003ej\u003c/sub\u003e.\n\u003c/p\u003e\u003cp\u003eThe j-th team can solve i-th problem if and only if T\u003csub\u003ej\u003c/sub\u003e + C\u003csub\u003ej\u003c/sub\u003e exceeds I\u003csub\u003ei\u003c/sub\u003e - O\u003csub\u003ei\u003c/sub\u003e. The team solves problems one after one, in the ascending order of expected solution time. Expected solution time for the problem is\n\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/2f98fdf67c48cc6b7d644529bd3acb38?v\u003d1714624534\"\u003e\u003c/center\u003e\nBut the actual time required to solve the problem is\n\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/28189151506d007dfb1edf2a12ac362f?v\u003d1714624534\"\u003e\u003c/center\u003e\nIf 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.\u003cp\u003e\u003c/p\u003e\n\u003cp\u003eIf 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.\u003c/p\u003e\n\u003cp\u003eThe 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.\u003c/p\u003e\n\u003cp\u003eThe 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.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThe first line of the input file contains m, n, t and l (1 \u0026lt;\u003d m \u0026lt;\u003d 16, 1 \u0026lt;\u003d n \u0026lt;\u003d 12, n \u0026lt;\u003d m, 1 \u0026lt;\u003d t \u0026lt;\u003d 20, 10 \u0026lt;\u003d l \u0026lt;\u003d 500).\u003c/p\u003e\n\u003cp\u003eThe following m lines describe problems, each line contains I\u003csub\u003ei\u003c/sub\u003e, A\u003csub\u003ei\u003c/sub\u003e, L\u003csub\u003ei\u003c/sub\u003e and O\u003csub\u003ei\u003c/sub\u003e (all numbers are integer, ranging from 1 to 1000, except L\u003csub\u003ei\u003c/sub\u003e which is from 100 to 50 000).\u003c/p\u003e\n\u003cp\u003eThe following t lines describe teams, each line contains T\u003csub\u003ej\u003c/sub\u003e, Z\u003csub\u003ej\u003c/sub\u003e , V\u003csub\u003ej\u003c/sub\u003e and C\u003csub\u003ej\u003c/sub\u003e (all numbers are integer, ranging from 1 to 1000).\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eOutput n integer numbers in the ascending order - the problems that must be selected.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e3 2 4 60\n20 40 2200 10\n60 10 600 10\n10 20 1500 40\n100 10 100 10\n100 30 70 2\n20 20 300 10\n30 1 100 1\n\u003c/pre\u003e\u003cp\u003e\n\u003c/p\u003e\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e2 3\n\u003c/pre\u003e\u003cp\u003e\n\n\u003cbr\u003e\n\u003c/p\u003e"}}]}