{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"en-us\"\u003eYou\u0026rsquo;ve finally got mad at \u0026ldquo;the world\u0026rsquo;s most stupid\u0026rdquo; employees of yours and decided to do some firings. You\u0026rsquo;re now simply too mad to give response to questions like \u0026ldquo;Don\u0026rsquo;t you think it is an even more stupid decision to have signed them?\u0026rdquo;, yet calm enough to consider the potential profit and loss from firing a good portion of them. While getting rid of an employee will save your wage and bonus expenditure on him, termination of a contract before expiration costs you funds for compensation. If you fire an employee, you also fire all his underlings and the underlings of his underlings and those underlings\u0026rsquo; underlings\u0026rsquo; underlings\u0026hellip; An employee may serve in several departments and his (direct or indirect) underlings in one department may be his boss in another department. Is your firing plan ready now?\u003c/span\u003e\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"en-us\"\u003eThe input starts with two integers \u003ci\u003en\u003c/i\u003e (0 \u0026lt; \u003ci\u003en\u003c/i\u003e \u0026le; 5000) and \u003ci\u003em\u003c/i\u003e (0 \u0026le; \u003ci\u003em\u003c/i\u003e \u0026le; 60000) on the same line. Next follows \u003ci\u003en\u003c/i\u003e + \u003ci\u003em\u003c/i\u003e lines. The first \u003ci\u003en\u003c/i\u003e lines of these give the net profit/loss from firing the \u003cspan data-scayt_word\u003d\"i-th\" data-scaytid\u003d\"1\"\u003e\u003ci\u003ei\u003c/i\u003e-th\u003c/span\u003e employee individually \u003ci\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e (|\u003ci\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e| \u0026le; 10\u003csup\u003e7\u003c/sup\u003e, 1 \u0026le; \u003ci\u003ei\u003c/i\u003e \u0026le; \u003ci\u003en\u003c/i\u003e). The remaining \u003ci\u003em\u003c/i\u003e lines each contain two integers \u003ci\u003ei\u003c/i\u003e and \u003ci\u003ej\u003c/i\u003e (1 \u0026le; \u003ci\u003ei\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e \u0026le; \u003ci\u003en\u003c/i\u003e) meaning the \u003cspan data-scayt_word\u003d\"i-th\" data-scaytid\u003d\"2\"\u003e\u003ci\u003ei\u003c/i\u003e-th\u003c/span\u003e employee has the \u003cspan data-scayt_word\u003d\"j-th\" data-scaytid\u003d\"3\"\u003e\u003ci\u003ej\u003c/i\u003e-th\u003c/span\u003e employee as his direct underling.\u003c/span\u003e\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\tOutput two integers separated by a single space: the minimum number of employees to fire to achieve the maximum profit, and the maximum profit.\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n5 5\r\n8\r\n-9\r\n-20\r\n12\r\n-10\r\n1 2\r\n2 5\r\n1 4\r\n3 4\r\n4 5\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n2 2\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\tAs of the situation described by the sample input, firing employees 4 and 5 will produce a net profit of 2, which is maximum.\u003c/div\u003e"}}]}