O que nos liga a todos? Bem, muitas vezes são as pontes. Desde a Antiguidade, as pessoas constroem pontes para estradas, comboios e peões, e aquedutos para transportar água. É a forma de a humanidade não se conformar com uma geografia inconveniente.

A empresa Arch Bridges Construction (ABC) especializa-se — adivinhou — na construção de pontes em arco. Este estilo clássico de ponte é sustentado por pilares que se erguem do solo por baixo da ponte. Os arcos entre os pilares distribuem o peso da ponte pelos pilares adjacentes.

Exemplo de uma ponte romana em arco. Fonte: Wikimedia Commons

As pontes construídas pela ABC têm frequentemente pilares espaçados a intervalos irregulares. Por razões estéticas, as pontes da ABC têm sempre arcos semicirculares, como ilustrado na Figura B.1. No entanto, embora um arco possa tocar no solo, não pode prolongar-se abaixo dele. Isto torna impossíveis algumas disposições dos pilares.

(a) Pilares consecutivos a uma distância $d$ são ligados por um arco semicircular de raio $r=d/2$.

(b) Uma disposição inválida de pilares (os arcos não podem prolongar-se abaixo do solo).

(c) Uma ponte correspondente à entrada do exemplo 1.

Figura B.1: Exemplos de pontes.

Dados um perfil do terreno e uma altura pretendida $h$ para a ponte, existem geralmente muitas formas de construir uma ponte em arco. Modelamos o perfil do terreno como uma função linear por troços descrita por $n$ pontos-chave $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$, em que a coordenada $x$ de um ponto é a posição ao longo da ponte e a coordenada $y$ é a elevação do terreno acima do nível do mar nessa posição. O primeiro e o último pilares têm de ser construídos no primeiro e no último pontos-chave, respetivamente, e os pilares intermédios só podem ser construídos nesses pontos-chave. O custo de uma ponte é o custo dos seus pilares (proporcional às suas alturas) mais o custo dos seus arcos (proporcional à quantidade de material utilizada). Assim, uma ponte com $k$ pilares de alturas $h_1,\ldots,h_k$, separados por distâncias horizontais $d_1,\ldots,d_{k-1}$, tem um custo total de

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

para certas constantes dadas $\alpha$ e $\beta$. A ABC quer construir cada ponte ao menor custo possível.

Entrada

A primeira linha da entrada contém quatro inteiros $n,h,\alpha,\beta$, em que $n$ ($2\le n\le 10^4$) é o número de pontos que descrevem o perfil do terreno, $h$ ($1\le h\le 10^5$) é a altura pretendida da ponte acima do nível do mar, e $\alpha,\beta$ ($1\le\alpha,\beta\le 10^4$) são os fatores de custo descritos anteriormente. Seguem-se $n$ linhas, a $i$-ésima das quais contém dois inteiros $x_i,y_i$ ($0\le x_1<x_2<\ldots<x_n\le 10^5$ e $0\le y_i<h$), que descrevem o perfil do terreno.

Saída

Apresente o custo mínimo de construir uma ponte desde a posição horizontal $x_1$ até $x_n$, à altura $h$ acima do nível do mar. Se for impossível construir qualquer ponte assim, apresente impossible.

Exemplos

Entrada 1

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

Saída 1

6460

Entrada 2

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

Saída 2

impossible