题目描述

佩奇周末利用网络，帮助猪爸爸完成一些简单的文件录入任务，任务通过邮件接收，这些邮件包含了猪爸爸的部门要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。 佩奇的总共帮忙时间为为 $n$ 分钟，从第 $1$ 分钟开始到第 $n$ 分钟结束。 现在总共有 $k$ 个任务： 1 如果同一个时刻，有多个任务可以选择，佩奇只能选择其中的一个； 2 如果一个时刻只有一个任务，则必须有佩奇来完成； 3 如果佩奇正在执行一个任务，无法接收别的任务； 每个任务有两个参数， $P$ 代表改任务是从第 $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≤n≤10^4,1≤k≤10^4,1≤p≤n,1≤p+t−1≤n$ 。