Qu'est-ce qui nous relie tous ? Eh bien, ce sont souvent les ponts. Depuis l'Antiquité, les humains construisent des ponts pour les routes, les trains et les piétons, ainsi que des aqueducs pour transporter l'eau. C'est leur façon de ne pas se laisser arrêter par une géographie peu commode.

L'entreprise Arch Bridges Construction (ABC) se spécialise — vous l'aurez deviné — dans la construction de ponts en arc. Ce style classique de pont est soutenu par des piliers qui s'élèvent depuis le sol sous le pont. Les arcs entre les piliers répartissent le poids du pont sur les piliers adjacents.

Exemple de pont romain en arc. Source : Wikimedia Commons

Les ponts construits par ABC ont souvent des piliers espacés à intervalles irréguliers. Pour des raisons esthétiques, les ponts d'ABC ont toujours des arcs en demi-cercle, comme l'illustre la Figure B.1. Toutefois, si un arc peut toucher le sol, il ne peut pas s'étendre en dessous. Cela rend certains placements de piliers impossibles.

(a) Deux piliers consécutifs distants de $d$ sont reliés par un arc en demi-cercle de rayon $r=d/2$.

(b) Un placement de piliers invalide (les arcs ne peuvent pas s'étendre sous le sol).

(c) Un pont correspondant à l'entrée d'exemple 1.

Figure B.1 : Exemples de ponts.

Étant donnés un profil du sol et une hauteur de pont souhaitée $h$, il existe généralement de nombreuses façons de construire un pont en arc. Nous modélisons le profil du sol par une fonction affine par morceaux décrite par $n$ points clés $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$, où la coordonnée $x$ d'un point donne la position le long du pont et sa coordonnée $y$ donne l'altitude du sol à cette position. Les premier et dernier piliers doivent être construits aux premier et dernier points clés, et les piliers intermédiaires ne peuvent être construits qu'à ces points clés. Le coût d'un pont est le coût de ses piliers (proportionnel à leurs hauteurs) plus celui de ses arcs (proportionnel à la quantité de matériau utilisée). Ainsi, un pont comprenant $k$ piliers de hauteurs $h_1,\ldots,h_k$, séparés par des distances horizontales $d_1,\ldots,d_{k-1}$, a pour coût total

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

pour des constantes données $\alpha$ et $\beta$. ABC veut construire chaque pont au coût le plus bas possible.

Entrée

La première ligne de l'entrée contient quatre entiers $n,h,\alpha,\beta$, où $n$ ($2\le n\le 10^4$) est le nombre de points décrivant le profil du sol, $h$ ($1\le h\le 10^5$) est l'altitude souhaitée du pont, et $\alpha,\beta$ ($1\le\alpha,\beta\le 10^4$) sont les coefficients de coût décrits précédemment. Suivent $n$ lignes, dont la $i$-ème contient deux entiers $x_i,y_i$ ($0\le x_1<x_2<\ldots<x_n\le 10^5$ et $0\le y_i<h$), décrivant le profil du sol.

Sortie

Affichez le coût minimal de construction d'un pont allant de la position horizontale $x_1$ à $x_n$ à une altitude $h$. S'il est impossible de construire un tel pont, affichez impossible.

Exemples

Entrée 1

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

Sortie 1

6460

Entrée 2

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

Sortie 2

impossible