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