21164_ProblemSolving

In easier times, Farmer John's cows had no problems. These days, though, they have problems, lots of problems; they have P (1 ≤ P ≤ 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 M (1 ≤ M ≤ 1000) money.

Their 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 ≤ payment ≤ M ) 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 ≤ payment ≤ M ). 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.

Since 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.

Determine the number of months it takes to solve all of the cows' problems and pay for the solutions.

* Line 1 : Two space-separated integers: M and P.

* Lines 2 ..P+1 : Line i+1 describes problem i with two space-separated integers: B_i and A_i. B_i is the payment to the consult BEFORE the problem is solved; A_i is the payment to the consult AFTER the problem is solved.

* Line 1 : The number of months it takes to solve and pay for all the cows' problems.

100 5
40 20
60 20
30 50
30 50
40 40

6

Input Details

The cows make 100 money each month. They have 5 problems to solve, which cost 40, 60, 30, 30, and 40 in advance to solve and then 20, 20, 50, 50, and 40 at the beginning of the month after the problems are solved.

Output Details

+------+-------+--------+---------+---------+--------+
|      | Avail | Probs  | Before  | After   | Candy  |
|Month | Money | Solved | Payment | Payment | Money  |
+------+-------+--------+---------+---------+--------+
| 1    | 0     | -none- | 0       | 0       | 0      |
| 2    | 100   | 1, 2   | 40+60   | 0       | 0      |
| 3    | 100   | 3, 4   | 30+30   | 20+20   | 0      |
| 4    | 100   | -none- | 0       | 50+50   | 0      |
| 5    | 100   | 5      | 40      | 0       | 60     |
| 6    | 100   | -none- | 0       | 40      | 60     |
+------+-------+--------+---------+---------+--------+