Dividing the Path

Farmer John's cows love the clover growing along the ridge of a hill in his field. To keep the clover watered, Farmer John installs water sprinklers along the ridge.

Model the ridge as a one-dimensional number line running from $0$ to $L$ (where $1 \le L \le 10^6$ and $L$ is even). Each sprinkler head sits on this line and waters the ground for some distance in both directions. A sprinkler's spray radius is an integer $r$ with $A \le r \le B$ (where $1 \le A \le B \le 1000$), so a sprinkler centered at position $x$ waters the closed segment $[x - r,\ x + r]$.

Farmer John must water the entire ridge so that every location is covered by exactly one sprinkler (no gaps and no overlap), and no sprinkler may spray past either end of the ridge. Equivalently, the sprinklers partition $[0, L]$ into consecutive segments, each of even length between $2A$ and $2B$.

Each of Farmer John's $N$ cows (where $1 \le N \le 1000$) has a favorite stretch of clover, given as the interval from $S$ to $E$; these stretches may overlap. Every cow's favorite stretch must be watered by a single sprinkler (that sprinkler may also spray beyond the stretch). Equivalently, no boundary between two adjacent sprinklers may fall strictly inside any cow's interval $(S, E)$.

Find the minimum number of sprinklers needed to water the entire ridge under these rules.

• Line 1: two space-separated integers $N$ and $L$.
• Line 2: two space-separated integers $A$ and $B$.
• Lines 3 through $N+2$: each line contains two integers $S$ and $E$ ($0 \le S < E \le L$), the start and end of one cow's favorite stretch, measured as distances from the start of the ridge.

• Line 1: the minimum number of sprinklers required. If no valid sprinkler configuration exists, output $-1$.

Consider the first example. Three sprinklers suffice: one centered at $1$ with radius $1$ (covering $[0, 2]$), one centered at $4$ with radius $2$ (covering $[2, 6]$), and one centered at $7$ with radius $1$ (covering $[6, 8]$). The middle sprinkler waters the entire stretch liked by the second cow ($3$ to $6$), and the last sprinkler waters the entire stretch liked by the first cow ($6$ to $7$).

                 |-----c2----|-c1|       cows' preferred ranges

     |---1---|-------2-------|---3---|   sprinklers

     +---+---+---+---+---+---+---+---+

     0   1   2   3   4   5   6   7   8