{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cbr\u003eMartian girl Kate has a toothache. The martian anatomy is very specific. They all have \u003ci\u003eN\u003c/i\u003e teeth, each situated on one of \u003ci\u003eK\u003c/i\u003e gums. Kate should pay dentist \u003ci\u003eA\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e mars euros for the treatment of \u003ci\u003ei\u003c/i\u003e-th tooth. Moreover, Kate should pay \u003ci\u003eB\u003c/i\u003e\u003csub\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e euros for the anesthesia of the gum \u003ci\u003ej\u003c/i\u003e if this gum has at least one tooth cured. What is the maximal number of teeth Kate can cure if parents gave her \u003ci\u003eP\u003c/i\u003e mars euros?\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eThe first line of the input contains three integer numbers \u003ci\u003eN\u003c/i\u003e, \u003ci\u003eK\u003c/i\u003e and \u003ci\u003eP\u003c/i\u003e (1≤ \u003ci\u003eN\u003c/i\u003e≤ 600; 1≤ \u003ci\u003eK\u003c/i\u003e≤ \u003ci\u003eN\u003c/i\u003e; 1≤ \u003ci\u003eP\u003c/i\u003e≤ 10\u003csup\u003e6\u003c/sup\u003e). The second line contains the sequence of \u003ci\u003eK\u003c/i\u003e integer numbers \u003ci\u003eB\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003eB\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e,..., \u003ci\u003eB\u003c/i\u003e\u003csub\u003e\u003ci\u003eK\u003c/i\u003e\u003c/sub\u003e, where \u003ci\u003eB\u003c/i\u003e\u003csub\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e is the cost of anesthesia of the \u003ci\u003ej\u003c/i\u003e-th gum (1≤ \u003ci\u003eB\u003c/i\u003e\u003csub\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e≤ 600 for all \u003ci\u003ej\u003c/i\u003e \u003d 1, 2,..., \u003ci\u003eK\u003c/i\u003e). Each of the following \u003ci\u003eN\u003c/i\u003e lines contains the description of tooth. Each description is the pair of integer numbers \u003ci\u003eA\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e and \u003ci\u003eC\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, where \u003ci\u003eA\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e is the cost of curing of the \u003ci\u003ei\u003c/i\u003e-th tooth, \u003ci\u003eC\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e is the number of the gum the tooth occupies (1≤ \u003ci\u003eA\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e≤ 600; 1≤ \u003ci\u003eC\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e≤ \u003ci\u003eK\u003c/i\u003e for all \u003ci\u003ei\u003c/i\u003e \u003d 1, 2,..., \u003ci\u003eN\u003c/i\u003e). \u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003eWrite to the first line of the output the maximal number of cured teeth \u003ci\u003eS\u003c/i\u003e. Write to the second line \u003ci\u003eS\u003c/i\u003e numbers of the cured teeth from the given set. If there are several solutions output any of them.\u003cbr\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2 10\n1 2\n1 2\n5 2\n3 1\n3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}