Irrigation Installation for Cow’s Favorite Grass

John’s cows have discovered that the grass along the ridge is exceptionally tasty. In order to keep the grass growing, John decides to install a number of sprinklers. To simplify the problem, the ridge can be considered a one‐dimensional number line of length \(L\) (with \(1\le L\le 10^6\)) and \(L\) is guaranteed to be even. Each sprinkler can water in both directions with a fixed integer range \(x\) where \(A\le x\le B\) (with \(1\le A\le B\le 10^3\)). When placed at an integer coordinate \(i\) with range \(x\), its watering interval is \([i-x,i+x]\); note that this interval must lie completely within \([0,L]\).

The entire ridge \([0,L]\) must be watered by a set of sprinklers. Their watering intervals must not overlap (that is, they form a partition of \([0,L]\) into contiguous segments) and each sprinkler’s interval has a length of \(2x\) (so the allowed segment lengths are even numbers in \([2A,2B]\)).

There are also \(N\) cows (\(1\le N\le 10^3\)), each with a favorite grass region \([S_i, E_i]\) (these regions may overlap between different cows). In the final setup, every cow’s favorite region must be irrigated by exactly one sprinkler – in other words, it must be completely contained in one of the sprinkler’s watering intervals (note that the endpoints may coincide with the boundaries).

Find the minimum number of sprinklers required to water the entire ridge while satisfying all constraints. If it is impossible, output -1.

Note:

• The coordinate line is marked from 0 to \(L\) (i.e. the coordinates range \(0\sim L\)).
• A sprinkler installed at coordinate \(i\) with range \(x\) covers \([i-x,i+x]\) and both \(i\) and \(x\) must be integers.
• The boundaries between sprinkler intervals (i.e. the endpoints of each segment) must be placed at even integers so that the sprinkler’s center \((L_i+R_i)/2\) is an integer.
• A boundary can coincide with a cow’s favorite region endpoint, but it cannot lie strictly inside any cow’s favorite interval.

inputFormat

The first line contains four integers: \(L\), \(A\), \(B\), and \(N\) — the length of the ridge, the minimum and maximum range of a sprinkler, and the number of cows, respectively.

Each of the following \(N\) lines contains two integers \(S_i\) and \(E_i\) representing the favorite interval of the \(i\)th cow.

It is guaranteed that \(L\) is even and \(0 \le S_i < E_i \le L\).

outputFormat

Output a single integer: the minimum number of sprinklers required to cover the entire ridge without overlapping watering intervals and such that every cow's favorite interval is completely contained in one sprinkler's interval. If no valid configuration exists, output -1.

sample

10 1 2 1
2 4

3