Extra
Time
BZOJ3389 安排值班 Time:1s Memory:50M AC:0% Submit:2

Description

一天有 T(1≤T≤10^6)个时段.约翰正打算安排他的 N(1≤N≤25000)只奶牛来值班,打扫打扫牛棚卫生.每只奶牛都有自己的空闲时间段[Si,Ei](1≤Si≤Ei≤T),只 能把空闲的奶牛安排出来值班.而且,每个时间段必需有奶牛在值班. 那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案, 就输出-1.

Input

第 1 行:N,T.

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

Output

最少安排的奶牛数.

Sample Input

3 10

1 7

3 6

6 10

Sample Output

2

样例说明

奶牛 1 和奶牛 3 参与值班即可.