Efficient Slabstones Rearrangement

Barbara has a garden. The garden is long and narrow, divided into $m$ equal-sized regions arranged in a row. Her friend, Babara, gave her $n$ slabstones as a birthday present. Barbara placed these slabstones in her garden so she can enjoy stepping from one slabstone to another every day. The $i$-th slabstone fully occupies regions $l_i$ to $r_i$. The slabstones do not overlap, and any two slabstones have at least $d$ empty regions between them.

Barbara recently bought another slabstone that occupies $x$ consecutive regions. She will shift the original slabstones within the garden, then place the new slabstone somewhere in the garden. After shifting the original slabstones and placing the new slabstone, the slabstones cannot overlap, and any two slabstones must have at least $d$ empty regions between them. The slabstones must also stay non-overlapping during the rearrangement.

Shifting a single slabstone to an adjacent region takes one minute. For example, the rearrangement above takes 4 minutes. Barbara wants to know the minimum possible total time required to rearrange the slabstones, so she can save time for other purposes.

The first line contains four integers $n$, $m$, $d$ and $x$. The $i$-th of the following $n$ lines contains two integers $l_i$ and $r_i$.

Print the minimum possible total time (in minutes) to rearrange the slabstones so the new slabstone can be placed in the garden. If the new slabstone cannot be placed in the garden no matter how the slabstones are rearranged, print $-1$.

• $1 \le n \le 2000$
• $1 \le d \le m \le 10^9$
• $1 \le x \le m \le 10^9$
• $1 \le l_i \le r_i \le m$ for $i \in \{1, 2, \dots, n\}$
• $r_i + d + 1 \le l_{i+1}$ for $i \in \{1, 2, \dots, n-1\}$. The slabstones are given in order from left to right.