题目描述

现在有 $n$ 个人提交代码给洛谷，其中第 $i$ 个人提交代码的时间是第 $l_i$ 秒至第 $r_i$ 秒 （包括第 $l_i,r_i$ 秒）。

小 H 可以进行若干次操作，每次操作选择两个正整数 $x,y$ 满足 $x\le y$，用 $y-x+1$ 的代价在区间 $[x,y]$ 所对应的时间，即第 $x$ 秒到第 $y$ 秒内 （包括第 $x,y$ 秒） 向洛谷发起 DDoS 攻击。小 H 可使用的总代价为 $m$。

小 H 希望所有的 $n$ 个人在提交代码时都全程受到 DDoS 攻击。

我们认为第 $i$ 个人提交代码时全程受到 DDoS 攻击，当且仅当对于 $\forall j\in[l_i,r_i]$，第 $j$ 秒有 DDoS 攻击。

由于小 H 讨厌不连续的攻击，所以他问你，他至少要进行几次操作，才能使得这 $n$ 个人提交代码时都全程受到 DDoS 攻击。

如果无论如何都不能使得这 $n$ 个人提交代码时都全程受到 DDoS 攻击，输出 $-1$。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，每行两个正整数 $l_i,r_i$。

输出格式

一个整数，表示最小的操作次数，无解输出 $\text{-1}$。

5 12
2 4
11 12
6 8
1 3
10 13

2

5 12
1 3
6 9
4 5
2 4
10 12

1

2 14
1 10
2 15

-1

提示

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1 \le n \le 10^6,1 \le m,l_i,r_i \le 10^9$。

$\text{Subtask}$	$n$	$m,l_i,r_i$	分值
$1$	$\le10$	$\le10^6$	$20$
$2$	$\le10^5$		$30$
$3$	$\le10^6$	$\le10^9$	$50$