城防

Format

在战争中,最最重要的保护住自己的主城。要想保护自己的主城最核心的是,给自己的主城城墙加固。

城主手下有\(n\)支工兵队伍。他给每支工兵队伍下达了不同的修建城墙任务。也就是给定城墙修建的起始位置和终止位置。对原有城墙进行加高\(1\)米的工作。注意,可以认为原位置原先均没有城墙。

请输出这\(n\)支工兵队伍修强工作完成后,最高的城墙高度是多少?

Input

第一行有两个变量,一个是修建的范围\(M\),即修建位置为\(0 - M\)。另外一个为\(n\),即工兵队伍数量。
后面\(n\)行,为给定的起始终止坐标(城主比较糊涂,起始和终止不一定谁大谁小)
\(M<= 1,000,000 ,n <= 30,000\)

Output

输出一个整数,表示最高的城墙高度

Sample 1

Input

10 2
1 5
5 10

Output

2

Limitation

\(1-5\)修\(1\)米
\(5-10\)修\(1\)米
最高的位置为\(5\),高度是\(2\)米。

Source

Vijos Original

信息

ID
1002
难度
7
分类
(无)
标签
递交数
1
已通过
0
通过率
0%
上传者