题目描述

小明每天上班前都会打开电脑，查看主管发来的邮件。邮件中列出了当天要完成的全部任务，每个任务有一个开始时刻和一个持续时间。

小明的工作日共 $n$ 分钟，从第 $1$ 分钟到第 $n$ 分钟。他到达后立刻开始工作。公司共有 $k$ 个任务需要完成。如果同一时刻有多个任务，小明可以任选一个来做，其余交给同事；如果只有一个任务，则必须由小明完成。若某任务开始时小明正在工作（被其他任务占用），该任务也交给同事。

某任务从第 $p$ 分钟开始，持续 $t$ 分钟，则它在第 $(p+t-1)$ 分钟结束。

编写程序计算小明如何选取任务，才能获得最大的空闲时间。

输入格式

第一行包含两个用空格隔开的整数 $n$ 和 $k$。

接下来 $k$ 行，每行两个用空格隔开的整数 $p$ 和 $t$，表示一个任务从第 $p$ 分钟开始，持续 $t$ 分钟。

输出格式

输出一行，包含一个整数，表示小明可能获得的最大空闲时间。

样例

15 6
1 2
1 6
4 11
8 5
8 1
11 5

4

提示

数据规模与约定

• 对于 $100\%$ 的数据，$1 \leq n \leq 10^4$，$1 \leq k \leq 10^4$，$1 \leq p \leq n$，$1 \leq p+t-1 \leq n$。