Mirko's Newspaper Time

Mirko's work shift lasts N minutes, and the minutes are numbered from 1 to N. He is given K jobs; each job is defined by a start time P and a duration T, meaning the job runs for T consecutive minutes, from minute P through minute P+T−1.

At every moment Mirko is either processing exactly one job or doing nothing and reading the newspaper. At the very start of his shift he is free (reading the newspaper).

The rules are:

• Whenever Mirko is free and one or more jobs start at that minute, he must immediately begin processing one of them. The other jobs that start at the same minute are handled by his co-workers.
• If another job starts while Mirko is busy processing a job, he cannot take that other job — not even after he finishes his current one, because it has already passed.
• When he finishes a job he becomes free again and reads the newspaper until the next job he is able to take begins.

By wisely choosing which job to take when several start at the same minute, Mirko can increase the time he spends reading. Compute the maximum number of minutes Mirko can spend reading the newspaper if he chooses optimally.

The first line contains two integers N and K (1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000). N is the length of the shift in minutes and K is the number of jobs.

Each of the next K lines contains two integers P and T, meaning that a job starts at minute P and lasts T minutes (1 ≤ P ≤ N, 1 ≤ P+T−1 ≤ N).

Print a single integer: the maximum number of minutes Mirko can spend reading the newspaper.