[ARC076F] Exhausted?

题意翻译

有 $m$ 个椅子在数轴上排列,第 $i$ 张椅子的坐标为i。 高桥君和他的朋友一共有 $n$ 个人。高桥君他们因为玩了太久的游戏,大家的腰和背都很痛,所以他们很有必要坐在椅子上休息一下。 高桥君他们每个人坐的椅子的坐标都很讲究,第 $i$ 个人想坐在坐标在 $l_i$ 以下(包括 $l_i$)的椅子上,或者坐在坐标在 $r_i$ 以上(包括 $r_i$)的椅子上。当然,一个的椅子只能坐一个人。 可这样计算下去,可能会让他们不能都坐在椅子上休息。青木君关心高桥君他们的健康,尽可能多地增加椅子,让高桥君他们都能够坐在椅子上休息。 椅子可以添加到任意的实数坐标上,请求出需要添加椅子数量的最小值。 ## 输入输出格式 ### 输入 第一行输入两个数 $n$ 和 $m$。 接下来的第二行到 $n+1$ 行依次输入 $l_i$ 和 $r_i$。 ### 输出 输出需要添加的椅子数量的最小值 ## 数据范围 $1 \leq N,M \leq 2\times 10^5$,$0\leq l_i < r_i \leq M+1$。所有的数都是整数 ## 样例解释 ### 样例一: $4$ 个人依次坐在坐标为 $3, 2, 1, 4$ 的椅子上,所以椅子不需要添加。 ### 样例二: 如果将椅子添加到坐标 $0$ 和 $7$,则可以将 $7$ 人按顺序放在坐标 $0, 5, 3, 2, 6, 1, 7$ 中。

题目描述

[problemUrl]: https://atcoder.jp/contests/arc076/tasks/arc076_d 椅子が $ M $ 個数直線上に並んでおり、$ i $ 番目の椅子 $ (1\ ≦\ i\ ≦\ M) $ は座標 $ i $ にあります。 高橋君が $ N $ 人います。高橋君たちはゲームのやりすぎで全員腰を痛めたため、どこかの椅子に座る必要があります。 各々の高橋君たちが座る椅子にはこだわりがあって、$ i $ 人目の高橋君は座標 $ L_i $ 以下、もしくは座標 $ R_i $ 以上の椅子に座りたいです。当然ながら、同じ椅子には $ 1 $ 人しか座れません。 このままでは、高橋君たち全員を椅子に座らせることができないかもしれません。 高橋君たちの健康管理に気を遣っている青木君は、椅子をできるだけ少ない数追加することで、 高橋君たち全員のこだわりを満たすように高橋君たちを椅子に座らせることができるようにしたいです。 椅子は、任意の実数座標に追加できます。追加する必要のある椅子の最小の個数を求めてください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ : $ $ L_N $ $ R_N $

输出格式


追加する必要のある椅子の最小の個数を出力せよ。

输入输出样例

输入样例 #1

4 4
0 3
2 3
1 3
3 4

输出样例 #1

0

输入样例 #2

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

输出样例 #2

2

输入样例 #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

说明

### 制約 - $ 1\ ≦\ N,M\ ≦\ 2\ ×\ 10^5 $ - $ 0\ ≦\ L_i\ <\ R_i\ ≦\ M\ +\ 1(1\ ≦\ i\ ≦\ N) $ - 入力は全て整数である ### Sample Explanation 1 $ 4 $ 人の高橋君を順に座標 $ 3,2,1,4 $ にある椅子に座らせることができるため、椅子を追加する必要はありません。 ### Sample Explanation 2 座標 $ 0 $ と $ 2.5 $ に椅子を追加すれば、$ 7 $ 人の高橋君を順に座標 $ 0,5,3,2,6,1,2.5 $ に座らせることができます。