最大化更新次数

时间限制：2s
空间限制：512MB

题目描述

有 $N$ 个格子横向排列，从左到右依次编号为 $1$ 到 $N$。最开始，所有格子都是白色。

你可以以任意顺序、任意次数进行以下 $M$ 种操作：第 $i$ 种操作会将第 $L_i$ 个格子到第 $R_i$ 个格子全部涂成黑色。如果某次操作使至少一个格子的颜色发生变化，就称这次操作改变了格子的状态。请你求出能够改变格子状态的操作次数的最大值。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行包含两个整数 $L_i,R_i$，表示第 $i$ 种操作涂黑的区间。

输出格式

输出一个整数，表示答案。

样例输入 1

3 3
1 3
1 1
3 3

样例输出 1

3

样例输入 2

4 3
1 2
3 4
1 4

样例输出 2

2

样例输入 3

5 5
4 5
1 1
2 4
1 2
2 5

样例输出 3

4

样例输入 4

20 15
2 4
16 19
7 13
1 15
3 18
10 11
1 10
1 7
14 16
1 16
2 17
1 17
12 14
3 17
4 10

样例输出 4

11

数据范围

对于所有数据，$1\le N\le 500$，$1\le M\le \frac{N(N+1)}2$，$1\le L_i\le R_i\le N$，并且所有区间 $(L_i,R_i)$ 两两不同。