分数: 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