{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn easier times, Farmer John\u0027s cows had no problems. These days, though, they have problems, lots of problems; they have \u003ci\u003eP\u003c/i\u003e (1 ≤ \u003ci\u003eP\u003c/i\u003e ≤ 300) problems, to be exact. They have quit providing milk and have taken regular jobs like all other good citizens. In fact, on a normal month they make \u003ci\u003eM\u003c/i\u003e (1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 1000) money.\u003c/p\u003e\u003cp\u003eTheir problems, however, are so complex they must hire consultants to solve them. Consultants are not free, but they are competent: consultants can solve any problem in a single month. Each consultant demands two payments: one in advance (1 ≤ \u003ci\u003epayment\u003c/i\u003e ≤ \u003ci\u003eM\u003c/i\u003e) to be paid at the start of the month problem-solving is commenced and one more payment at the start of the month after the problem is solved (1 ≤ \u003ci\u003epayment\u003c/i\u003e ≤ \u003ci\u003eM\u003c/i\u003e). Thus, each month the cows can spend the money earned during the previous month to pay for consultants. Cows are spendthrifts: they can never save any money from month-to-month; money not used is wasted on cow candy.\u003c/p\u003e\u003cp\u003eSince the problems to be solved depend on each other, they must be solved mostly in order. For example, problem 3 must be solved before problem 4 or during the same month as problem 4.\u003c/p\u003e\u003cp\u003eDetermine the number of months it takes to solve all of the cows\u0027 problems and pay for the solutions.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Line 1: Two space-separated integers: \u003ci\u003eM\u003c/i\u003e and \u003ci\u003eP\u003c/i\u003e.\r\u003cbr\u003eLines 2..\u003ci\u003eP\u003c/i\u003e+1: Line \u003ci\u003ei\u003c/i\u003e+1 describes problem \u003ci\u003ei\u003c/i\u003e with two space-separated integers: \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e. \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the payment to the consult BEFORE the problem is solved; \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the payment to the consult AFTER the problem is solved.\r\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Line 1: The number of months it takes to solve and pay for all the cows\u0027 problems."}},{"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\u003e100 5\r\n40 20\r\n60 20\r\n30 50\r\n30 50\r\n40 40\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cpre\u003e\u003cp\u003e+------+-------+--------+---------+---------+--------+\u003cbr\u003e|\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | Avail | Probs\u0026nbsp; | Before\u0026nbsp; | After\u0026nbsp;\u0026nbsp; | Candy\u0026nbsp; |\u003cbr\u003e|Month | Money | Solved | Payment | Payment | Money\u0026nbsp; |\u003cbr\u003e+------+-------+--------+---------+---------+--------+\u003cbr\u003e| 1\u0026nbsp;\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | -none- | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; |\u003cbr\u003e| 2\u0026nbsp;\u0026nbsp;\u0026nbsp; | 100\u0026nbsp;\u0026nbsp; | 1, 2\u0026nbsp;\u0026nbsp; | 40+60\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; |\u003cbr\u003e| 3\u0026nbsp;\u0026nbsp;\u0026nbsp; | 100\u0026nbsp;\u0026nbsp; | 3, 4\u0026nbsp;\u0026nbsp; | 30+30\u0026nbsp;\u0026nbsp; | 20+20\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; |\u003cbr\u003e| 4\u0026nbsp;\u0026nbsp;\u0026nbsp; | 100\u0026nbsp;\u0026nbsp; | -none- | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 50+50\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; |\u003cbr\u003e| 5\u0026nbsp;\u0026nbsp;\u0026nbsp; | 100\u0026nbsp;\u0026nbsp; | 5\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 40\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 60\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; |\u003cbr\u003e| 6\u0026nbsp;\u0026nbsp;\u0026nbsp; | 100\u0026nbsp;\u0026nbsp; | -none- | 0\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 40\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | 60\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; | \u003cbr\u003e+------+-------+--------+---------+---------+--------+\u003c/p\u003e\u003c/pre\u003e"}}]}