← 返回题目列表

Codeforces · 1132/C

C. 粉刷栅栏

中文机器翻译题面 查看原题

你有一个由 $$$n$$$ 部分组成的长栅栏。不幸的是,它没有上漆,所以你决定雇佣 $$$q$$$ 画家来给它上漆。第 $$$i$$$ 个画家将绘制所有 $$$x$$$ 部分,使得 $$$l_i \le x \le r_i$$$。

不幸的是,您的预算很紧张,因此您可能只雇用 $$$q - 2$$$ 画家。显然,只有您雇用的油漆工才会做他们的工作。

如果您最佳地选择 $$$q - 2$$$ 画家,则您希望最大化绘制部分的数量。如果至少有一名画家绘制了某个部分,则该部分被视为已绘制。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$3 \le n, q \le 5000$$$) — 分别是可雇用的部分数量和油漆工数量。

接下来是 $$$q$$$ 行,每行描述一位画家:$$$i$$$ 第行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。

输出

打印一个整数 - 如果您雇用 $$$q - 2$$$ 油漆工,则绘制部分的最大数量。

示例

输入 #1

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

输出 #1

7

输入 #2

4 3
1 1
2 2
3 4

输出 #2

2

输入 #3

4 4
1 1
2 2
2 3
3 4

输出 #3

3