Home => ProblemSet => 2.10-35:区间覆盖
Problem1601--2.10-35:区间覆盖

1601: 2.10-35:区间覆盖

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 −1。

Input

第一行包含两个整数 s 和 t,表示给定线段区间的两个端点。
第二行包含整数 N,表示给定区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。

Output

输出一个整数,表示所需最少区间数。
如果无解,则输出 −1。

Sample Input Copy

1 5
3
-1 3
2 4
3 5

Sample Output Copy

2

HINT









1≤N≤105,
−109≤ai≤bi≤109,
−109≤s≤t≤109

Source/Category