{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn a certain week, a company wants to finish \u003ci\u003em\u003c/i\u003e projects. To this end, the company can employ at most \u003ci\u003en\u003c/i\u003e people from the unemployment agency for a period of one week. Each external employee will cost the company \u003ctt\u003esalary\u003c/tt\u003e euro, unless the project in which he/she is involved is not completed in time. In that case no payment is due.\u003c/p\u003e\u003cp\u003eFor each project the company knows from experience the probability that the project will be completed within a week, as a function of the number of employees working on it. These probabilities are given as percentages \u003ci\u003ep\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e, where \u003ci\u003ei\u003c/i\u003e (with 1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003em\u003c/i\u003e) is the number of the project and \u003ci\u003ej\u003c/i\u003e is the number of people working on it. Of course, when nobody is working on a project \u003ci\u003ei\u003c/i\u003e, the probability \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e is zero percent.\u003c/p\u003e\u003cp\u003eIf project \u003ci\u003ei\u003c/i\u003e is indeed finished within a week, the company earns \u003ctt\u003ereward\u003c/tt\u003e(\u003ci\u003ei\u003c/i\u003e) euro; if it is not ready in time, the company has to pay a fine of \u003ctt\u003epunishment\u003c/tt\u003e(\u003ci\u003ei\u003c/i\u003e) euro.\u003c/p\u003e\u003cp\u003eOf course the company wants to maximise its total expected profit\u003csup\u003e1\u003c/sup\u003e at the end of the week by finding the optimal number of external employees to hire, and how to divide them over the projects. The optimal number of employees is the total number of people needed to achieve the maximal expected profit. Your task in this matter is to calculate this optimal number of external employees. Remember that at most \u003ci\u003en\u003c/i\u003e people are available. Furthermore: if a person is employed, he/she works on one and only one project.\u003c/p\u003e\u003chr noshade width\u003d\"30%\" align\u003d\"left\" size\u003d\"1\" color\u003d\"#000000\"\u003e\u003cp\u003e\u003csmall\u003e\u003csup\u003e1\u003c/sup\u003eLet \u003ci\u003ep\u003c/i\u003e (0 \u0026lt; \u003ci\u003ep\u003c/i\u003e \u0026lt; 1) be the probability that a job is finished in time, and let \u003ci\u003eE\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e be the profit in that case. Furthermore, let \u003ci\u003eE\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e be the (negative) profit in case the job is not finished in time. Then the expected profit for this particular job is \u003ci\u003ep\u003c/i\u003e⋅\u003ci\u003eE\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e + (1 − \u003ci\u003ep\u003c/i\u003e)⋅\u003ci\u003eE\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e.\u003c/small\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:\u003c/p\u003e\u003cul\u003e\u003cli\u003eOne line with one integer \u003ci\u003em\u003c/i\u003e with 1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 100: the number of projects.\u003c/li\u003e\u003cli\u003eOne line with one integer \u003ci\u003en\u003c/i\u003e with 0 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100: the maximal number of available employees.\u003c/li\u003e\u003cli\u003eOne line with one integer salary with 0 ≤ \u003ctt\u003esalary\u003c/tt\u003e ≤ 1,000: the salary of one employee. Remember that the salary is given in euros.\u003c/li\u003e\u003cli\u003e\u003ci\u003em\u003c/i\u003e lines, each line corresponding to a project \u003ci\u003ei\u003c/i\u003e, containing \u003ci\u003en\u003c/i\u003e integers \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, …, \u003ci\u003ep\u003csub\u003ein\u003c/sub\u003e\u003c/i\u003e (the percentages, with 0 ≤ \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, …, \u003ci\u003ep\u003csub\u003ein\u003c/sub\u003e\u003c/i\u003e ≤ 100), followed by two integers corresponding to the \u003ctt\u003ereward\u003c/tt\u003e and the \u003ctt\u003epunishment\u003c/tt\u003e for project \u003ci\u003ei\u003c/i\u003e. All values are separated by single spaces. Both \u003ctt\u003ereward\u003c/tt\u003e and \u003ctt\u003epunishment\u003c/tt\u003e are given in euros and are between 0 and 100,000 (boundaries included).\u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor every test case in the input file, the output should contain two lines.\u003c/p\u003e\u003cul\u003e\u003cli\u003eThe first line contains the maximal expected profit in eurocents.\u003c/li\u003e\u003cli\u003eThe second line contains the total number of external employees that must be hired in order to achieve this maximal expected profit. If the maximal expected profit can be achieved by different (total) numbers of employees, then these different numbers must be given in increasing order. Numbers have to be separated by single spaces.\u003c/li\u003e\u003c/ul\u003e"}},{"title":"Sample","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\u003e3\r\n1\r\n4\r\n200\r\n90 100 100 100 2000 0\r\n2\r\n2\r\n100\r\n80 80 2100 500\r\n0 100 1700 500\r\n3\r\n4\r\n100\r\n100 80 80 70 1000 100\r\n100 90 80 90 500 50\r\n100 70 60 50 700 100\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e162000\r\n1\r\n100000\r\n1 2\r\n190000\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}