本题没有可用的提交语言。

描述

克里斯有限公司（Chris Ltd.）正在准备一款名为“最大值生成器（Maximizer）”的新型排序硬件。最大值生成器有$n$个输入，编号从$1$到$n$。每个输入代表一个整数。最大值生成器有一个输出，该输出代表最大值生成器所有输入中出现的最大值。

最大值生成器是由一系列排序器$Sorter(i_1, j_1), \ldots, Sorter(i_k, j_k)$组成的流水线来实现的。每个排序器都有$n$个输入和$n$个输出。排序器$Sorter(i, j)$会对输入$i, i + 1, \ldots, j$上的值按非递减顺序进行排序，而让其他输入的值保持不变直接通过。最后一个排序器的第$n$个输出就是最大值生成器的输出。

一位实习生（曾是ACM竞赛选手）发现，流水线中的某些排序器可以被移除，而最大值生成器仍然能产生正确的结果。对于所有可能的输入值组合，在给定的流水线中排序器的初始序列里，能仍然产生正确结果的最短子序列的长度是多少呢？

任务

编写一个程序，该程序：

1. 读取最大值生成器的描述，即流水线中排序器的初始序列；
2. 计算在初始的排序器序列中，对于所有可能的输入数据仍能产生正确结果的最短子序列的长度；
3. 输出结果。

输入

输入的第一行包含两个整数$n$和$m$（$2 \leq n \leq 50000$，$1 \leq m \leq 500000$），它们之间用单个空格分隔。整数$n$是输入的数量，整数$m$是流水线中排序器的数量。接下来的$m$行描述了排序器的初始序列。其中第$k$行包含第$k$个排序器的参数：两个整数$i_k$和$j_k$（$1 \leq i_k < j_k \leq n$），它们之间用单个空格分隔。

输出

输出仅由一行组成，包含一个整数，该整数等于在初始的排序器序列中，对于所有可能的数据仍能产生正确结果的最短子序列的长度。

输入数据 1

40 6
20 30
1 10
10 20
20 30
15 25
30 40

输出数据 1

4

提示

输入数据量巨大，建议使用scanf。

来源

2003年中欧竞赛