¿Qué nos conecta a todos? Pues a menudo son los puentes. Desde la antigüedad, las personas han construido puentes para carreteras, trenes y peatones, y acueductos para transportar agua. Es la forma que tiene la humanidad de no resignarse ante una geografía inconveniente.

La empresa Arch Bridges Construction (ABC) se especializa, como habrás adivinado, en construir puentes de arco. Este estilo clásico de puente se apoya en pilares que se elevan desde el suelo situado bajo el puente. Los arcos entre los pilares distribuyen el peso del puente entre los pilares adyacentes.

Ejemplo de un puente de arco romano. Fuente: Wikimedia Commons

Los puentes construidos por ABC suelen tener pilares separados por intervalos irregulares. Por motivos estéticos, los puentes de ABC siempre tienen arcos semicirculares, como se ilustra en la Figura B.1. Sin embargo, aunque un arco puede tocar el suelo, no puede extenderse por debajo de él. Esto hace imposibles algunas ubicaciones de los pilares.

(a) Los pilares consecutivos separados por una distancia $d$ están conectados por un arco semicircular de radio $r=d/2$.

(b) Una ubicación de pilares no válida (los arcos no pueden extenderse por debajo del suelo).

(c) Un puente correspondiente a la entrada de ejemplo 1.

Figura B.1: Ejemplos de puentes.

Dados un perfil del terreno y una altura deseada del puente $h$, normalmente hay muchas maneras de construir un puente de arco. Modelamos el perfil del terreno como una función lineal a trozos descrita por $n$ puntos clave $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$, donde la coordenada $x$ de un punto es la posición a lo largo del puente y su coordenada $y$ es la elevación del terreno sobre el nivel del mar en esa posición. El primer y el último pilar deben construirse en el primer y el último punto clave, respectivamente, y los pilares intermedios solo se pueden construir en estos puntos clave. El coste de un puente es el coste de sus pilares (proporcional a sus alturas) más el coste de sus arcos (proporcional a la cantidad de material utilizado). Por tanto, un puente con $k$ pilares de alturas $h_1,\ldots,h_k$, separados por distancias horizontales $d_1,\ldots,d_{k-1}$, tiene un coste total de

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

para unas constantes dadas $\alpha$ y $\beta$. ABC quiere construir cada puente al menor coste posible.

Entrada

La primera línea de la entrada contiene cuatro enteros $n,h,\alpha,\beta$, donde $n$ ($2\le n\le 10^4$) es el número de puntos que describen el perfil del terreno, $h$ ($1\le h\le 10^5$) es la altura deseada del puente sobre el nivel del mar, y $\alpha,\beta$ ($1\le\alpha,\beta\le 10^4$) son los factores de coste descritos anteriormente. A continuación hay $n$ líneas; la $i$-ésima contiene dos enteros $x_i,y_i$ ($0\le x_1<x_2<\ldots<x_n\le 10^5$ y $0\le y_i<h$), que describen el perfil del terreno.

Salida

Imprime el coste mínimo de construir un puente desde la posición horizontal $x_1$ hasta $x_n$ a una altura $h$ sobre el nivel del mar. Si es imposible construir un puente así, imprime impossible.

Ejemplos

Entrada 1

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

Salida 1

6460

Entrada 2

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

Salida 2

impossible