P1280 Nick's Task

Before going to work each day, Nick connects to the Internet and receives emails from his supervisor. These emails list all tasks that Nick’s department must complete that day. Each task is defined by a start time and a duration. Nick’s workday lasts $n$ minutes, from minute $1$ to minute $n$. As soon as Nick arrives at work, he starts working. There are $k$ tasks in total. If, at the same moment, multiple tasks need to be done, Nick may choose any one of them to do, and the others will be completed by his colleagues. Conversely, if there is only one task, then that task must be done by Nick. If some tasks start at a time when Nick is already working, those tasks will also be handled by his colleagues. If a task starts at minute $p$ and lasts $t$ minutes, then it ends at minute $(p+t-1)$. Write a program to determine how Nick should choose tasks in order to maximize his free time.

The first line contains two integers $n$ and $k$ separated by a space. Each of the next $k$ lines contains two integers $p$ and $t$, indicating a task that starts at minute $p$ and lasts $t$ minutes.

Output a single line containing one integer, the maximum free time Nick can obtain.

Constraints - For 100% of the testdata, it is guaranteed that $1 \leq n \leq 10^4, 1 \leq k \leq 10^4, 1 \leq p \leq n, 1 \leq p+t-1 \leq n$. Translated by ChatGPT 5