A7070 | $Welcome24ever 和喷灌器$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Welcome24ever 的奶牛们发现山脊上的草特别美味。为维持草的生长，Welcome24ever 打算在山脊上安装若干喷灌器。 将山脊看成一条一维数轴，范围为 $[0,L]$，其中 $L$ 为偶数，且 $1 \le L \le 10^6$。 每个喷灌器必须满足： 位置是整数 $p$； 射程（半径）是整数 $x$，且 $A \le x \le B$（$1 \le A \le B \le 10^3$）； 它的灌溉范围是 $[p-x,\,p+x]$，并且必须完全落在山脊范围内，即 $0 \le p-x$ 且 $p+x \le L$。 现在要求： 1. 山脊上的每一个位置都必须被灌溉到； 2. 任意两个喷灌器的灌溉区间不允许重叠（端点相接不算重叠）； 3. 有 $N$ 只奶牛（$1 \le N \le 10^3$），第 $i$ 只奶牛最喜欢的草区是区间 $[S_i,E_i]$（$1 \le S_i E_i \le L$），不同奶牛的草区可以重叠； 4. 每只奶牛的草区必须“只被一个喷灌器灌溉”，也就是说：对每个 $i$，存在某个喷灌器的灌溉区间完全覆盖 $[S_i,E_i]$。 请你求出最少需要多少个喷灌器；如果无法做到，输出 $-1$。

第一行包含两个整数 $N, L$。 第二行包含两个整数 $A, B$。 接下来 $N$ 行，每行包含两个整数 $S_i, E_i$。

输出一行一个整数，表示最少喷灌器数量；如果无解输出 $-1$。

输入 #1

输出 #1

C++ 编辑器

输入

输出