Network Relay Optimization

In this problem, you are given a scenario where a mobile company, several base stations, and the up host's house are all located on the same straight line. The mobile company is the source of the signal and base stations can relay this signal towards the up host's house. Each base station is equipped with two circular ranges tangent to the ground: a fixed transmit range with radius (r) and an adjustable receive range with radius (r'). For a base station (i) located at (x_i) to receive a signal from a previous station (j) (with (x_j < x_i)), the receiving circle of station (i) must be externally tangent to the transmitting circle of station (j). Formally, if station (i) sets its receive radius to (r'_i), then the centers of the two circles are ((x_i, r'_i)) and ((x_j, r)) respectively and the tangency condition gives [ \sqrt{(x_i-x_j)^2+(r'_i-r)^2} = r'_i + r \quad \Longrightarrow \quad (x_i-x_j)^2 = 4r,r'_i, ] which implies [ r'_i = \frac{(x_i-x_j)^2}{4r}\quad \text{and} \quad \text{extra cost} = \sqrt{r'_i} = \frac{x_i-x_j}{2\sqrt{r}}. ]

In addition, activating any base station (i) incurs a starting cost (v_i). To deliver the signal to the up host's house, it is enough that there exists a base station whose transmitting circle (with radius (r)) touches or intersects the vertical line at the up host’s position (U); that is, for that station (i) we require (|x_i-U| \le r).

The signal chain must start at the mobile company (located at coordinate (M)) and then follow an increasing sequence of base stations (i.e. if station (j) transmits to station (i) then (x_j < x_i)). The cost to connect mobile company to a station (i) directly is (\frac{x_i-M}{2\sqrt{r}}+v_i). For a chain connecting mobile company (\to) station (j_1) (\to) station (j_2) (\to) ... (\to) station (j_k) (where station (j_k) is chosen such that (|x_{j_k} - U| \le r)), the total cost is the sum over each connection of the extra cost plus the activation costs of the stations used. Note that if the mobile company itself is within distance (r) of the up host (i.e. (|M-U| \le r)), then no chain is needed and the total cost is 0.

Your task is to choose a subset of base stations (if needed) and design the relay chain such that the total cost is minimized. If it is impossible to deliver the signal under the given constraints, output -1.

Input Format: The first line contains four numbers: an integer (n) (the number of base stations), and three numbers (M, U, r) representing the x-coordinate of the mobile company, the x-coordinate of the up host's house, and the fixed transmit radius of every base station respectively. Then follow (n) lines, each containing two numbers (x_i) and (v_i), representing the x-coordinate and activation cost of the (i)-th base station.

Output Format: Output a single number representing the minimal total cost to deliver the signal from the mobile company to the up host's house. If it is impossible, output -1.

Note: All formulas are given in (\LaTeX) format.

inputFormat

The first line contains four space-separated numbers: (n) (number of base stations), (M) (x-coordinate of the mobile company), (U) (x-coordinate of the up host's house), and (r) (fixed transmit radius). Each of the following (n) lines contains two space-separated numbers: (x_i) and (v_i) — the x-coordinate and activation cost of the (i)-th base station.

outputFormat

Output a single number — the minimal total cost required to relay the signal from the mobile company to the up host's house. If it is impossible to establish such a chain, output -1.

sample

2 0 5 10
3 5
7 3

0