logo AlgoBeat OnlineJudge
登录 注册

#103389. [BZOJ 3389] [Usaco2004 Dec]Cleaning Shifts安排值班

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一天有T(1≤T≤10^6)个时段.约翰正打算安排他的N(1≤N≤25000)只奶牛来值班,打扫

打扫牛棚卫生.每只奶牛都有自己的空闲时间段Si,Ei,只能把空闲的奶牛安排出来值班.而且,每个时间段必需有奶牛在值班. 那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案,就输出-1.

输入格式

第1行:N,T.

第2到N+1行:Si,Ei.

输出格式

最少安排的奶牛数.

样例

样例输入

3  10
1  7
3  6
6  10

样例输出

    2


样例说明
    奶牛1和奶牛3参与值班即可.