← 返回题目列表

AtCoder · arc076_d

F. 筋疲力尽?

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

分数: 1000 点

问题陈述

有 M 椅子排成一排。的坐标 i第椅子 (1 ≤ i ≤ M) is i.

N 高桥家的人玩游戏太多了,都腰疼了。他们需要坐在椅子上休息,但他们对坐哪张椅子有讲究。具体来说, i第一个人希望坐在坐标不大于的椅子上 L_i,或不少于 R_i。当然,同一张椅子上只能坐一个人。

如果不采取任何措施,他们可能无法坐在自己最喜欢的椅子上。 关心高桥家人们健康的青木决定提供额外的椅子,以便大家都可以坐在自己喜欢的位置上。

额外的椅子可以放置在任意真实坐标处。找出所需的最少额外椅子数量。

约束

  • 1 ≤ N,M ≤ 2 × 10^5
  • 0 ≤ L_i < R_i ≤ M + 1(1 ≤ i ≤ N)
  • 所有输入值均为整数。

输入

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

N M
L_1 R_1
:
L_N R_N

输出

打印所需的最少额外椅子数量。


示例输入 1

4 4
0 3
2 3
1 3
3 4

示例输出 1

0

四人可以坐在坐标处的椅子上 3, 2, 1 和 4分别,并且不再需要椅子。


示例输入 2

7 6
0 7
1 5
3 6
2 7
1 6
2 6
3 7

示例输出 2

2

如果我们在坐标处放置额外的椅子 0 和 2.5,七个人可以坐在坐标处 0, 5, 3, 2, 6, 1 和 2.5。


示例输入 3

3 1
1 2
1 2
1 2

示例输出 3

2

示例输入 4

6 6
1 6
1 6
1 5
1 5
2 6
2 6

示例输出 4

2