P3662 - 划区灌溉

题目

P3662划区灌溉

限制 : 时间限制 : 10000 MS 空间限制 : 65536 KB

问题描述

约翰的奶牛们发现山脊上的草特别美味．为了维持草的生长，约翰打算安装若干喷灌器．为简化问题，山脊可以看成一维的数轴，长为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说明：

来源 usaco 2004 dec gold