5975: 进阶7.9.6 洒水装置-2
内存限制：128 MB
时间限制：10.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
在一片草场上:有一条长度为L ( 1 ≤ L ≤ 1 , 000 , 000 L (1 leq L leq 1,000,000L(1≤L≤1,000,000，L LL为偶数) ))的线段。 John的N ( 1 ≤ N ≤ 1000 ) N (1 leq N leq 1000)N(1≤N≤1000) 头奶牛都沿着草场上这条线段吃草，每头牛的活动范围是一个开区间( S , E ) (S,E)(S,E)， S SS， E EE都是整数。不同奶牛的活动范围可以有重叠。John要在这条线段上安装喷水头灌溉草场。每个喷水头的喷洒半径可以随意调节，调节范围是 [ A , B ] ( 1 ≤ A ≤ B ≤ 1000 ) [A, B](1 leq A leq B leq 1000)[A,B](1≤A≤B≤1000)， A , B A,BA,B都是整数。要求线段上的每个整点恰好位于一个喷水头的喷洒范围内每头奶牛的活动范围要位于一个喷水头的喷洒范围内任何喷水头的喷洒范围不可越过线段的两端(左端是 0 00，右端是 L LL )。
请问， John 最少需要安装多少个喷水头。
请问， John 最少需要安装多少个喷水头。
输入
第1 11行：整数N NN、 L LL。
第2 22行：整数A AA、 B BB。
第3 33到N + 2 N+2N+2行：每行两个整数S SS、 E ( 0 ≤ S < E ≤ L ) E (0 leq S < E leq L)E(0≤S<E≤L)，表示某头牛活动
范围的起点和终点在线段上的坐标(即到线段起点的距离)。
第2 22行：整数A AA、 B BB。
第3 33到N + 2 N+2N+2行：每行两个整数S SS、 E ( 0 ≤ S < E ≤ L ) E (0 leq S < E leq L)E(0≤S<E≤L)，表示某头牛活动
范围的起点和终点在线段上的坐标(即到线段起点的距离)。
输出
最少需要安装的多少个喷水头；若没有符合要求的喷水头安装方案
，则输出-1。
样例解释：
|-----c2----|-c1| cows' preferred ranges |---1---|-------2-------|---3---| sprinklers +---+---+---+---+---+---+---+---+ 0 1 2 3 4 5 6 7 8
样例输入 复制
2 8
1 2
6 7
3 6样例输出 复制
3