P3662划区灌溉 | |
|
问题描述
约翰的奶牛们发现山脊上的草特别美味.为了维持草的生长,约翰打算安装若干喷灌器.为简化问题,山脊可以看成一维的数轴,长为L( \(1≤L≤10^6\) ), 而且L-定是一个偶数.
每个喷灌器可以双向喷灌,并有确定的射程,该射程不短于A,不长于B,A,B( \(1≤A≤B≤10^3\))都是给出的正整数.它所在位置的两边射程内,都属它的灌溉区域.注意,一个喷灌器往左右两边喷射的距离是一样的,比如往左喷的距离是x,那么往右也是x,(A<=x<=B)。
现要求山脊的每一个区域都被灌溉到,喷灌器不能将水喷到山脊以外的区域,而且喷灌器的灌溉区域不允许重叠, 约翰有N( $1≤N≤10^3$ )只奶牛,每一只都有特别喜爱的草区,第i奶牛喜爱的草区是[Si,Ei],不同奶牛的草区可以重叠(Ei-Si<=2*B).
现要求,每只奶牛的草区仅被一个喷灌器灌溉. 寻找最少需要的喷灌器数目.
输入格式
第一行,两个整数N和L
第二行,两个整数A和B
接下来N行,每行两个整数S和E(0 <= S < E <= L),表示每头奶牛喜欢的草区的起止位置
输出格式
一行,一个整数,表示最少需要的喷灌器的数量,若无解,输出-1
样例输入
样例输入1:
2 8
1 2
6 7
3 6
样例输入2:
4 202
10 12
21 27
32 39
103 121
163 180
样例输出
样例输出1:
3
样例输出2:
10
提示
样例1说明:
|-----c2----|-c1| 每头奶牛喜欢的区域
|---1---|-------2-------|---3---| 喷灌器
+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8
来源 usaco 2004 dec gold