题目描述

出题人今天和他的小组成员一起完成一个小组课题，而这个课题又分为 $k$ 个任务，每个任务有固定的开始时刻和用时。

这个小组课题预计用时 $n$ 分钟，从第 $1$ 分钟开始到第 $n$ 分钟结束。紧张又有(hun)序(luan)的小组课题开始后出题人就需要开始干活。这个小组课题一共有 $k$ 个任务需要完成。如果在同一时刻有多个任务需要解决，出题人可以看自己的心情来任选其中的一个来做，而其余的任务就可以美滋滋地丢给其它小组同学来完成，如果只有一个任务，则该任务一定得由出题人去完成。假如有些任务开始的时候出题人已经在干活了，则这些任务也可以丢给他的小组同学。如果第 $i$ 个任务于第 $p_i$ 分钟开始，持续时间为 $t_i$ 分钟，则该任务将在第 $(p_i+t_i-1)$ 分钟结束（结束的那个时刻也要干活！）。

说明：每个人不能丢下他 or 她干了一半的活。

出题人比较关心的是当他完成了一个任务，但是没有马上开始的任务让他做的情况，在这种情况下，出题人就可以爽快地摸鱼到有新的任务需要做。

但是出题人摸鱼摸傻了，于是他来请教你他在这个课题里面至多能够摸鱼多少分钟（即多少的时间没有活干）。😁😁😁

输入格式

第一行含为两个整数 $n$ 和 $k$，含义如题面所示。

接下来共有 $k$ 行，每一行有两个用空格隔开的整数 $p_i$ 和 $t_i$ ，含义如题面所示。

输出格式

一个整数，表示出题人至多能摸鱼几分钟。

18 6
4 11
1 2
3 5
6 8
6 2
11 5

6

提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^4,1 \leq k \leq 10^4,1 \leq p_i \leq n,1 \leq p_i+t_i-1 \leq n$。