You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

国王的国度有 $N$ 堵城墙和 $M$ 个炮塔。第 $i$ 个炮塔守卫着第 $L_i$ 到第 $R_i$ 堵城墙。

求至少摧毁多少个炮塔，使得至少一堵城墙没有被任何一个瞭望塔守卫。

输入格式

第一行两个整数 $N,M(1\le N\le 10^6,1\le M\le 2\times 10^5)$。
接下来 $M$ 行，每行两个整数 $L_i,R_i(1\le L_i\le R_i\le N)$。

输出格式

一行一个整数表示答案。

样例1

输入

10 4
1 6
4 5
5 10
7 10

输出

1

样例2

输入

5 2
1 2
3 4

输出

0

样例3

输入

5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3

输出

3

样例解释

对于第一个样例，摧毁炮塔 $1$ 后，城墙 $3$ 无炮塔守卫。不摧毁炮塔时任何城墙均有炮塔守卫，故答案为 $1$。

对于第二个样例，没有炮塔守卫城墙 $5$，你不需要摧毁任何炮塔。故答案为 $0$。

数据分布

$40\%$的数据，$(1\le N\le 100,1\le M\le 10)$，$L_i,R_i(1\le L_i\le R_i\le N)$。

$100\%$的数据，$(1\le N\le 10^6,1\le M\le 2\times 10^5)$，$L_i,R_i(1\le L_i\le R_i\le N)$。

时空限制

• 时间限制：$1s$
• 空间限制：$256M$