Maximizing Free Time

Nick connects to the Internet every morning before work and receives an email from his boss containing all the tasks that need to be completed by his department for the day. Each task is characterized by a start time and a duration. Nick's workday lasts for n minutes, starting at minute 1 and ending at minute n. There are a total of k tasks scheduled.

The rules are as follows:

• If at a certain minute when Nick is free there is exactly one task starting, then he must do that task.
• If more than one task starts at the same minute when Nick is free, he may choose at most one of them to do; the remaining tasks will be handled by his colleagues. In order to maximize his free time, Nick may opt not to take any task when several are available.
• If a task starts while Nick is already occupied (i.e. working on a task), then that task will be handled by his colleagues.

Note that if a task starts at minute \( p \) and has a duration of \( t \) minutes, it finishes at minute \( p+t-1 \). Nick wants to maximize his idle time during the workday by choosing which optional tasks to perform.

Write a program to calculate the maximum number of minutes that Nick can remain idle.

inputFormat

The first line contains two integers \( n \) and \( k \), representing the total number of minutes in the workday and the number of tasks, respectively.

The next \( k \) lines each contain two integers \( p \) and \( t \), where \( p \) is the start minute of a task and \( t \) is its duration in minutes.

outputFormat

Output a single integer representing the maximum free (idle) time Nick can achieve.

sample

10 3
1 3
2 2
4 3

4