← 返回题目列表

AtCoder · arc168_d

D. 最大化更新

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

分数: 700 点

问题陈述

有 N 方块排成一排,编号 1 to N 从左到右。 最初,所有方块都是白色的。

您可以执行以下操作 M 操作类型 以任意顺序任意次数:

  • 类型-i 操作:绘制方块 L_i 穿过广场 R_i 黑色。

求操作可以改变方块状态的最大次数。 如果一项操作改变了至少一个方块的颜色,则该操作被视为改变了方块的状态。

约束

  • 1 \leq N \leq 500
  • 1 \leq M \leq 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
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

打印答案。


示例输入 1

3 3
1 3
1 1
3 3

示例输出 1

3

如果执行以下操作,它们将改变方块的状态三次。

  • 执行类型-2 操作。广场 1 新漆成黑色。
  • 执行类型-3 操作。广场 3 新漆成黑色。
  • 执行类型-1 操作。广场 2 新漆成黑色。

示例输入 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