Dividing the Path

Interview

Time limit1sMemory limit128 MB

Summary

Partition the segment [0, L] into consecutive pieces of even length between 2A and 2B so no cut lands strictly inside any cow's interval, and minimize the number of pieces, or report that no partition exists.

Level: Medium6 of 10
Topics: Dynamic programming, Prefix sum, Sliding window, Intervals
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Notes

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

Examples3

Example 1
Input
```
2 8
1 2
6 7
3 6
```
Expected output
```
3
```
Example 2
Input
```
1 4
1 2
1 3
```
Expected output
```
1
```
Example 3
Input
```
1 10
1 2
1 9
```
Expected output
```
-1
```