金牌厨师

题号：NC232585
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Phenix作为食堂的金牌厨师，每天的工作是为同学们准备饭菜，Phenix做出的每一种菜都有一个辣度值，范围是 $[1,n]$ 。作为厨师，Phenix提前了解了m位同学的辣度接受范围，第i位同学的辣度接受范围被描述为 $[l_i,r_i]$ ，表示该同学可以接受辣度值位于这个区间的菜。由于众口难调，每天Phenix会选出部分同学，做出能让这部分同学都接受的辣度的菜。Phenix作为金牌厨师对每天工作的满意程度定义为选出的同学的人数 $k$ 和能让这部分同学都接受的菜的种类数 $x$ （这里理解为一种辣度对应一种菜）两者中的最小值，即 $min(k,x)$ $n,m$ $(1<=n,m<=300000)$ 。

现在你需要想办法让Phenix的满意程度最大。

输入描述:

第一行两个整数 $n,m$ ，表示菜的辣度最大值和同学的人数 $(1<=n,m<=300000)$ 。

接下来 $m$ 行,每行两个整数 $l_i,r_i$ 依次表示第 $i$ 个同学的辣度接受范围 $(1<=l_i,r_i<=n)$

输出描述:

一行，表示满意度的最大值。

示例1

输入

复制

输出

复制

说明

最优策略为：选择第1，3，4位同学，他们的辣度接受范围分别是[3,5],[2,5],[2,5]，所以能让他们都接受的菜的辣度是3，4，5，此时k=3,x=3,满意度=min(k,x)=3