Description

John’s cows have discovered that the grass on the ridge is especially tasty. To sustain its growth, John plans to install several sprinklers.

To simplify the problem, the ridge is modeled as a one-dimensional number line of length $L\ (1\le L\le 10^6)$, and $L$ is guaranteed to be even. Each sprinkler sprays in both directions with a fixed radius that is at least $A$ and at most $B$, where $A, B\ (1\le A\le B\le 10^3)$ are given positive integers. The interval within its radius on both sides of its position is its irrigation area.

The entire ridge must be irrigated, and irrigation areas of different sprinklers are not allowed to overlap. John has $N\ (1\le N\le 10^3)$ cows, each with a favorite grass interval. The $i$-th cow’s interval is $[S_i,E_i]$, and different cows’ intervals may overlap. Each cow’s favorite interval must be irrigated by exactly one sprinkler, i.e., it must be entirely contained in the irrigation range of a single sprinkler.

Note:

1. The number line for $L$ is labeled starting from $0$ (i.e., the coordinate range is $0\sim L$).
2. Sprinkler coordinates and radii must be integers. For a sprinkler at coordinate $i$ with radius $x$, its irrigation interval is $[i-x,i+x]$.
3. The irrigated interval must lie within the ridge. For example, you cannot place a sprinkler with radius $1$ at position $0$.

Find the minimum number of sprinklers required.

Input Format

The first line contains two integers $N,L$.

The second line contains two integers $A,B$.

Then follow $N$ lines, each containing two integers $S_i,E_i$（$1\le S_i < E_i\le L$）.

Output Format

Output a single line with the minimum number of sprinklers required. If it is impossible to design a valid sprinkler configuration for Farmer John, output $-1$.

2 8
1 2
6 7
3 6

3

Hint

Constraints:

• For $100\%$ of the testdata, $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$.

Sample explanation:

Translated by ChatGPT 5