#P1545. [USACO04DEC] Dividing the Path G
[USACO04DEC] Dividing the Path G
题目描述
约翰的奶牛们发现山脊上的草特别美味。为了维持草的生长,约翰打算安装若干喷灌器。
为简化问题,山脊可以看成一维的数轴,长为 ,而且 一定是一个偶数。每个喷灌器可以双向喷灌,并有确定的射程,该射程不短于 ,不长于 ,, 都是给出的正整数。它所在位置的两边射程内,都属它的灌溉区域。
现要求山脊的每一个区域都被灌溉到,而且喷灌器的灌溉区域不允许重叠。约翰有 只奶牛,每一只都有特别喜爱的草区,第 奶牛的草区是 ,不同奶牛的草区可以重叠。现要求,每只奶牛的草区仅被一个喷灌器灌溉。
注意:
- 数轴 从 开始标记(即坐标范围 )
- 喷灌器坐标和射程必须为整数,对于坐标为 射程为 的喷灌器,它的灌溉范围为 。
- 浇灌区间必须在山脊范围内。例如,不能在 位置放一个半径为 的浇灌器。
寻找最少需要的喷灌器数目。
输入格式
第一行两个整数 。
第二行两个整数 。
然后 行每一行两个整数 ()。
输出格式
一行,输出所需的最少洒水器数量。如果无法为农夫约翰设计喷头配置,则输出 。
2 8
1 2
6 7
3 6
3
提示
对于 的数据,,,,。
样例解释: