UOJ Logo AYIT Online Judge

AYITOJ

#95. 勤劳的老黄牛

统计
时间限制:1s    内存限制:256M    满分: 20分

题目描述

鲁迅说过;“横眉冷对千夫指,俯首甘为孺子牛”,王点点家就有这样 N 头辛勤的老黄牛。

但是牛也是有脾气的,他们只在自己固定的时间劳作,王点点想要找出一些牛,让这些牛劳作时间可以覆盖掉1到T这个时间段(即开始时间为1,结束时间为T)。

聪明的你能否告诉我如果要在这1到T的时间段内完成任务需要的最小的老黄牛数量。(某个老黄牛的结束时间可能会超过T)

输入描述

N,T。表示 N头牛 ,T个时间点。

接下来 N行,每行两个数字a,b表示每头牛工作的开始时间和结束时间。

输出描述

符合条件的最小的牛的数量,如果没有符合条件的输出-1。

样例输入

3 10
1 7
3 6
6 10

样例输出

2


数据范围

$1 <= N <= 10000,1 <= T <= 10^5,1 <= a <= b <= 10^5$

题目来源

CXY_