Beautiful Bridges

What connects us all? Often, it is bridges. Since ancient times, people have built bridges for roads, for trains, for pedestrians, and as aqueducts to carry water. It is humanity's way of not accepting inconvenient geography as an answer.

The company Arch Bridges Construction (ABC) specializes in, as the name suggests, the construction of arch bridges. This classical style of bridge is supported by pillars that extend from the ground below the bridge. Arches between pillars distribute the bridge's weight onto the adjacent pillars.

Bridges built by ABC often have pillars spaced at irregular intervals. For aesthetic reasons, ABC's bridges always have semicircular arches, as Figure B.1 shows. However, a bridge arch can touch the ground but cannot extend below the ground. This makes some pillar placements impossible.

(a) Consecutive pillars at distance d are connected by a semicircular arch with radius r = d/2.	(b) An invalid pillar placement (arches cannot extend below ground).	(c) A bridge corresponding to Sample Input 1.

Figure B.1: Bridge examples.

Given a ground profile and a desired bridge height h, there are usually many ways to build an arch bridge. We model the ground profile as a piecewise-linear function described by n key points (x1, y1),(x2, y2), . . . ,(xn, yn), where the x-coordinate of a point is the position along the bridge, and the y-coordinate is the elevation of the ground above sea level at this position along the bridge. The first and last pillars must be built at the first and last key points, and intermediate pillars can be built only at these key points. The cost of a bridge is the cost of its pillars (proportional to their heights) plus the cost of its arches (proportional to the amount of material used). So a bridge with k pillars of heights h1, . . . , hk separated by horizontal distances d1, . . . , dk−1 has total cost

[\alpha \cdot \sum_{i=1}^{k}{h_i} + \beta \cdot \sum_{i=1}^{k-1}{d_i^2}]

for given constants α and β. ABC wants to build each bridge at the lowest possible cost.

The first line of input contains four integers n, h, α, and β, where n (2 ≤ n ≤ 104) is the number of points describing the ground profile, h (1 ≤ h ≤ 105) is the desired height of the bridge above sea level, and α, β (1 ≤ α, β ≤ 104) are the cost factors described earlier. Then follow n lines, the ith of which contains two integers xi, yi (0 ≤ x1 < x2 < . . . < xn ≤ 105 and 0 ≤ yi < h), describing the ground profile.

Output the minimum cost of building a bridge from horizontal position x1 to xn at height h above sea level. If no such bridge can be built, output impossible.