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