题目描述

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

你可以以任意顺序、任意次数进行以下 $M$ 种操作：

• 第 $i$ 种操作：将第 $L_i$ 个格子到第 $R_i$ 个格子涂成黑色。

请你求出能够改变格子状态的操作次数的最大值。注意，如果某次操作使得至少有一个格子的颜色发生了变化，则认为该操作改变了格子的状态。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

输出格式

请输出答案。

样例 1

输入

3 3
1 3
1 1
3 3

输出

3

样例 2

输入

4 3
1 2
3 4
1 4

输出

2

样例 3

输入

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

输出

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

输出

11

说明/提示

限制条件

• $1 \leq N \leq 500$
• $1 \leq M \leq \frac{N(N+1)}{2}$
• $1 \leq L_i \leq R_i \leq N$
• $(L_i, R_i) \neq (L_j, R_j)$（$i \neq j$）
• 输入的所有值均为整数。

样例解释 1

如下操作可以使格子的状态发生变化的操作次数为 $3$ 次。

• 执行第 $2$ 种操作。第 $1$ 个格子被新涂成黑色。
• 执行第 $3$ 种操作。第 $3$ 个格子被新涂成黑色。
• 执行第 $1$ 种操作。第 $2$ 个格子被新涂成黑色。

由 ChatGPT 4.1 翻译