#P1668. [USACO04DEC] Cleaning Shifts S

[USACO04DEC] Cleaning Shifts S

题目描述

一天有 T(1T106)T(1\le T\le 10^6) 个时段。约翰正打算安排他的 N(1N2.5×104)N(1\le N\le 2.5\times 10^4) 只奶牛来值班,打扫打扫牛棚卫生。每只奶牛都有自己的空闲时间段 [Si,Ei](1SiEiT) [S_i,E_i](1\le S_i\le E_i\le T),只能把空闲的奶牛安排出来值班。而且,每个时间段必需有奶牛在值班。

那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案,就输出 1-1

输入格式

11 行:NNTT

22N+1N+1 行:SiS_iEiE_i

输出格式

一行,输出最少安排的奶牛数。

3 10
1 7
3 6
6 10
2

提示

1T1061\le T\le 10^6N2.5×104N\le 2.5\times 10^41SiEiT1\le S_i\le E_i\le T