Description

In the past, Farmer John's cows had no problems to solve. But now they have problems—lots of problems. To be precise, they have P (1 <= P <= 300) problems to solve. They have also left the farm and found jobs like ordinary people. Their monthly salary is M (1 <= M <= 1000) dollars.

Their problems are top-tier challenges, so they need to hire helpers. Helpers are not free, but they can guarantee solving any problem within one month. Each problem requires two payments: the first payment A_i (1 <= A_i <= M) is paid at the beginning of the month when the problem is being solved, and the second payment B_i (1 <= B_i <= M) is paid at the beginning of the following month after the problem is solved. Each month, the cows use the money they earned from the previous month to make these payments. The cows have no savings habits, so any leftover money from the previous month is spent on candy.

Because the problems are interrelated, they must be solved in roughly sequential order. For example, problem 3 must be solved before or in the same month as problem 4.

Find the minimum number of months required for the cows to solve all problems and complete all payments.

Input Format

• Line 1: M and P
• Lines 2...P+1: Line i+1 contains A_i and B_i, representing the upfront payment and completion payment for the i-th problem, respectively.

Output Format

• Line 1: The minimum number of months required for the cows to solve all problems and complete all payments.

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

6

Hint

【Input Explanation】

The cows' monthly salary is 100 yuan. They have 5 problems to solve, with expected payments of 40, 60, 30, 30,40, and completed payments of 20, 20, 50, 50, 40.

【Output Explanation】

| Month | Amount | Problems Solved | Last Month's Payment | This Month's Payment | Balance |

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

Source

USACO Monthly Contest