配点 : $1000$ 点

問題文

椅子が $M$ 個数直線上に並んでおり、$i$ 番目の椅子 $(1 \leq i \leq M)$ は座標 $i$ にあります。

高橋君が $N$ 人います。高橋君たちはゲームのやりすぎで全員腰を痛めたため、どこかの椅子に座る必要があります。 各々の高橋君たちが座る椅子にはこだわりがあって、$i$ 人目の高橋君は座標 $L_i$ 以下、もしくは座標 $R_i$ 以上の椅子に座りたいです。当然ながら、同じ椅子には $1$ 人しか座れません。

このままでは、高橋君たち全員を椅子に座らせることができないかもしれません。 高橋君たちの健康管理に気を遣っている青木君は、椅子をできるだけ少ない数追加することで、 高橋君たち全員のこだわりを満たすように高橋君たちを椅子に座らせることができるようにしたいです。

椅子は、任意の実数座標に追加できます。追加する必要のある椅子の最小の個数を求めてください。

制約

• $1 \leq N,M \leq 2 \times 10^5$
• $0 \leq L_i < R_i \leq M + 1(1 \leq i \leq N)$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$L_1$ $R_1$

$:$

$L_N$ $R_N$

出力

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

4 4
0 3
2 3
1 3
3 4

0

$4$ 人の高橋君を順に座標 $3,2,1,4$ にある椅子に座らせることができるため、椅子を追加する必要はありません。

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

2

座標 $0$ と $2.5$ に椅子を追加すれば、$7$ 人の高橋君を順に座標 $0,5,3,2,6,1,2.5$ に座らせることができます。

3 1
1 2
1 2
1 2

2

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

2