No submission language available for this problem.

自习时间

题目描述

小码君需要去参加一门重要的考试，于是他不得不安排较多的时间去自习。

但是学校安排了一些课程，小码君每天上课共 $T$ 分钟，从第 $1$ 分钟开始到第 $T$ 分钟结束，他想在这 $T$ 分钟里安排更多的时间去自习。

假设某堂课于第 $A$ 分钟开始，时长 $W$ 分钟，该堂课于第 $A+W-1$ 分钟结束。

如果小码君在这门课的开始时刻不在教室内，他就会迟到。

小码君只能在每门课开始时刻进入教室（过了时间不再允许进入教室），并且要完整地上完这门课，上课时如果其他课开始，他不用去上课。如果当前时刻小码君没有在上课，而且此时是某几堂课的开始时刻，那么他必须选择其中一门去上课。

显然，选择不同的课小码君的能够利用起来的自习时间就不同，小码君想利用尽可能多的时间来自习，请你帮他计算他最多能自习多久。

输入格式

输入的第一行为两个整数 $T、N$，代表小码君今天上课 $T$ 分钟，共有 $N$ 堂课。

接下来 $N$ 行每行两个整数，分别是 $A,W$ ，代表这堂课从第 $A$ 分钟开始，上课时长 $W$ 分钟。

输出格式

输出为一行，代表小码君最长的自习时间。

样例 #1

样例输入 #1

10 3
1 5
1 4
5 5

样例输出 #1

5

样例 #2

样例输入 #2

14 7
1 3
1 2
3 5
3 4
4 8
6 2
7 3

样例输出 #2

7

提示

【数据规模】

对于百分百的数据

$1 <= T,N <= 10^4$

$1<=A<=T$

$1<=A+W-1<=T$

Background

Special for beginners, ^_^

Description

Given two integers x and y, print the sum.

Format

Input

Two integers x and y, satisfying $0\leq x,y\leq 32767$ .

Output

One integer, the sum of x and y.

Samples

123 500

623

Limitation

1s, 1024KiB for each test case.