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$ 根无限长的梁，编号从 $1\sim m$。呆呆熊 准备偷这些梁来替换自己的柱。

假设柱子每一厘米都是一段，呆呆熊 会按照编号从小到大的顺序依次操作，会使用编号为 $i$ 的梁替换自己柱子的第 $l_i\sim r_i$ 段。

请问最终 呆呆熊 的柱子包含了几种不同编号的梁。

输入格式

第一行为空格隔开的两个整数 $n,m$。

接下来 $m$ 行，第 $i$ 行为空格隔开的两个整数 $l_i,r_i$。

输出格式

输出一个整数，即最终 33DAI 的柱子包含了几种不同编号的梁。

7 3
2 6
3 5
4 4

3

假设从左往右是第 $1$ 段到第 $n$ 段，0 表示原始柱子，1~m 表示 m 根梁的替换部分，则替换过程如下：

0000000 -> 0111110 -> 0122210 -> 0123210

最终有三种梁出现在了柱子上。

7 5
1 7
1 5 
1 3
1 6
1 3

3

替换过程如下：

0000000 -> 1111111 -> 2222211 -> 3332211 -> 4444441 -> 5554441

最终有三种梁出现在了柱子上。

7 3
1 6
2 7
3 5

3

替换过程如下：

0000000 -> 1111110 -> 1222222 -> 1233322

最终有三种梁出现在了柱子上。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m \le 5000$，$1\le l_i\le r_i\le n$。

• 子任务 1（10 分）：保证替换区域没有重叠。
• 子任务 2（20 分）：保证 $l_i=r_i$。
• 子任务 3（30 分）：保证 $l_i=1$。
• 子任务 4（40 分）：没有特殊限制。