Problem Solving

The cows have $P$ problems to solve ($1 \le P \le 300$). They have quit producing milk and taken regular jobs like everyone else, and in a normal month they earn $M$ money ($1 \le M \le 1000$).

Their problems are so complex that they must hire consultants to solve them. Consultants are competent: a consultant can solve any single problem in one month. Each consultant demands two payments — one in advance, paid at the start of the month in which work on the problem begins, and one afterward, paid at the start of the month after the problem is solved.

Each month the cows may pay consultants only with the money earned during the previous month. The cows are spendthrifts: they can never carry money over to the next month, and any money not spent is wasted on cow candy. Thus the amount available to spend each month is exactly $M$, and in the first month there is no previous month, so no money is available.

Because the problems depend on one another, they must be solved essentially in order. For example, problem 3 must be solved before problem 4, or at the latest during the same month as problem 4. In other words, the problems solved in any single month always form a contiguous range of problem numbers.

Determine the minimum number of months needed to solve every problem and pay every consultant in full.

• Line 1: Two space-separated integers, $M$ and $P$.
• Lines 2 through $P+1$: Line $i+1$ describes problem $i$ with two space-separated integers $B_i$ and $A_i$. $B_i$ is the advance payment made before the problem is solved and $A_i$ is the payment made after the problem is solved, with $1 \le B_i \le M$ and $1 \le A_i \le M$.

• Line 1: The minimum number of months needed to solve every problem and pay for the solutions.

The table below traces the process for the example input. The money available each month is $100$, and no money is available in the first month.

+-------+-------+--------+---------+---------+--------+
|       | 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   |
+-------+-------+--------+---------+---------+--------+

So solving all problems and paying for them takes $6$ months.