#P2684. 搞清洁

搞清洁

题目描述

FJ 准备分配它的 NN 只奶牛 (1N2.5×104)(1 \le N \le 2.5\times 10^4) 做清洁工作,他把一天分成 T(1T106)T(1 \le T \le 10^6) 个时间段,他希望每一个时间段都有奶牛在清洁,但搞清洁的奶牛数越少越好。

输入格式

第一行,两下整数 NNTT

接下来 NN 行,每行两个整数,表示第 ii 头奶牛能工作的时间段。

输出格式

使每一个时间段都有奶牛工作的最少奶牛数,如果不可能,则输出 -1

3 10
1 7
3 6
8 10

2


提示

样例解释:

33 头奶牛,第 11 头能工作的时间段是 171\sim7,即从时间 11 开始工作,时间 77 结束(时间 77 也在工作的),第 22 头是 363\sim6,第 33 头是 8108\sim10,则只需要第 11 头和第 33 头奶牛就能使每一个时间都有奶牛工作。