题目描述

农夫约翰要安排他的(N)（(1 ≤ N ≤ 25000)）头奶牛在谷仓周围做一些清洁工作。他总是希望有一头奶牛在做清洁工作，并且他把一天分成了(T)个班次（(1 ≤ T ≤ 1000000)），第一个班次是第(1)班，最后一个班次是第(T)班。

每头奶牛在一天中的某些时间段内可以参与清洁工作。任何被选中做清洁工作的奶牛都会在她的整个可用时间段内工作。

你的任务是帮助农夫约翰为各个班次安排一些奶牛，以便（i）每个班次至少有一头奶牛被安排；（ii）参与清洁工作的奶牛数量尽可能少。如果不可能为每个班次都安排一头奶牛，则输出(-1)。

输入

第(1)行：两个用空格分隔的整数：(N)和(T)

第(2)行到第(N + 1)行：每行包含一头奶牛可以工作的时间段的开始时间和结束时间。一头奶牛从开始时间开始工作，并在结束时间之后结束工作。

输出

第(1)行：农夫约翰需要雇佣的最少奶牛数量，如果不可能为每个班次都安排一头奶牛，则输出(-1)。

3 10
1 7
3 6
6 10

2

提示

这个问题有大量的输入数据，使用scanf()而不是cin来读取数据，以避免时间限制超出。

输入详情：

有(3)头奶牛和(10)个班次。奶牛(1)可以在第(1)到第(7)个班次工作，奶牛(2)可以在第(3)到第(6)个班次工作，奶牛(3)可以在第(6)到第(10)个班次工作。

输出详情：

通过选择奶牛(1)和奶牛(3)，所有班次都被覆盖了。没有办法用少于(2)头奶牛覆盖所有的班次。

来源

USACO 2004 年 12 月银牌赛