Was verbindet uns alle? Nun, oft sind es Brücken. Seit der Antike bauen Menschen Brücken für Straßen, Züge und Fußgänger sowie Aquädukte zum Wassertransport. So weigert sich die Menschheit, eine unbequeme Geografie einfach hinzunehmen.

Das Unternehmen Arch Bridges Construction (ABC) ist — wie zu erwarten — auf den Bau von Bogenbrücken spezialisiert. Dieser klassische Brückenstil wird von Pfeilern getragen, die vom Boden unterhalb der Brücke emporragen. Bögen zwischen den Pfeilern verteilen das Gewicht der Brücke auf die benachbarten Pfeiler.

Beispiel einer römischen Bogenbrücke. Quelle: Wikimedia Commons

Die von ABC gebauten Brücken haben oft unregelmäßige Abstände zwischen ihren Pfeilern. Aus ästhetischen Gründen haben die Brücken von ABC stets halbkreisförmige Bögen, wie in Abbildung B.1 dargestellt. Ein Brückenbogen darf den Boden zwar berühren, aber nicht unter ihn reichen. Dadurch sind manche Pfeilerplatzierungen unmöglich.

(a) Aufeinanderfolgende Pfeiler im Abstand $d$ werden durch einen halbkreisförmigen Bogen mit Radius $r=d/2$ verbunden.

(b) Eine ungültige Pfeilerplatzierung (Bögen dürfen nicht unter den Boden reichen).

(c) Eine Brücke zur Beispieleingabe 1.

Abbildung B.1: Brückenbeispiele.

Für ein gegebenes Bodenprofil und eine gewünschte Brückenhöhe $h$ gibt es gewöhnlich viele Möglichkeiten, eine Bogenbrücke zu bauen. Wir modellieren das Bodenprofil als stückweise lineare Funktion, beschrieben durch $n$ Stützpunkte $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$. Die $x$-Koordinate eines Punktes gibt die Position entlang der Brücke an, seine $y$-Koordinate die Höhe des Bodens über dem Meeresspiegel an dieser Position. Der erste und der letzte Pfeiler müssen am ersten bzw. letzten Stützpunkt gebaut werden; Zwischenpfeiler dürfen ebenfalls nur an diesen Stützpunkten gebaut werden. Die Kosten einer Brücke sind die Kosten ihrer Pfeiler (proportional zu deren Höhen) plus die Kosten ihrer Bögen (proportional zur verwendeten Materialmenge). Eine Brücke mit $k$ Pfeilern der Höhen $h_1,\ldots,h_k$, deren horizontale Abstände $d_1,\ldots,d_{k-1}$ betragen, hat somit Gesamtkosten von

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

für gegebene Konstanten $\alpha$ und $\beta$. ABC möchte jede Brücke zu möglichst geringen Kosten bauen.

Eingabe

Die erste Eingabezeile enthält vier ganze Zahlen $n,h,\alpha,\beta$. Dabei ist $n$ ($2\le n\le 10^4$) die Anzahl der Punkte, die das Bodenprofil beschreiben, $h$ ($1\le h\le 10^5$) die gewünschte Höhe der Brücke über dem Meeresspiegel und $\alpha,\beta$ ($1\le\alpha,\beta\le 10^4$) sind die zuvor beschriebenen Kostenfaktoren. Es folgen $n$ Zeilen, von denen die $i$-te zwei ganze Zahlen $x_i,y_i$ ($0\le x_1<x_2<\ldots<x_n\le 10^5$ und $0\le y_i<h$) zur Beschreibung des Bodenprofils enthält.

Ausgabe

Gib die minimalen Kosten für den Bau einer Brücke von der horizontalen Position $x_1$ bis $x_n$ in der Höhe $h$ über dem Meeresspiegel aus. Falls keine solche Brücke gebaut werden kann, gib impossible aus.

Beispiele

Eingabe 1

5 60 18 2
0 0
20 20
30 10
50 30
70 20

Ausgabe 1

6460

Eingabe 2

4 10 1 1
0 0
1 9
9 9
10 0

Ausgabe 2

impossible