Apa yang menghubungkan kita semua? Sering kali, jawabannya adalah jembatan. Sejak zaman dahulu, manusia membangun jembatan untuk jalan, kereta api, pejalan kaki, serta akuaduk untuk mengalirkan air. Itulah cara manusia menolak menyerah kepada geografi yang menyulitkan.

Perusahaan Arch Bridges Construction (ABC) berspesialisasi dalam — tebakan Anda benar — pembangunan jembatan lengkung. Gaya jembatan klasik ini ditopang oleh pilar-pilar yang menjulang dari tanah di bawah jembatan. Lengkungan di antara pilar menyalurkan berat jembatan ke pilar-pilar yang bersebelahan.

Contoh jembatan lengkung Romawi. Sumber: Wikimedia Commons

Jembatan yang dibangun ABC sering memiliki pilar dengan jarak yang tidak beraturan. Demi keindahan, jembatan ABC selalu memiliki lengkungan setengah lingkaran, seperti ditunjukkan pada Gambar B.1. Namun, meskipun lengkungan jembatan boleh menyentuh tanah, lengkungan itu tidak boleh masuk ke bawah permukaan tanah. Akibatnya, beberapa penempatan pilar tidak mungkin dilakukan.

(a) Pilar berurutan yang berjarak $d$ dihubungkan oleh lengkungan setengah lingkaran berjari-jari $r=d/2$.

(b) Penempatan pilar yang tidak valid (lengkungan tidak boleh masuk ke bawah tanah).

(c) Jembatan yang sesuai dengan contoh masukan 1.

Gambar B.1: Contoh-contoh jembatan.

Diberikan profil tanah dan ketinggian jembatan yang diinginkan $h$, biasanya ada banyak cara untuk membangun jembatan lengkung. Kita memodelkan profil tanah sebagai fungsi linear sepotong-sepotong yang dijelaskan oleh $n$ titik kunci $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$, dengan koordinat $x$ menyatakan posisi sepanjang jembatan dan koordinat $y$ menyatakan ketinggian tanah di atas permukaan laut pada posisi tersebut. Pilar pertama dan terakhir harus dibangun pada titik kunci pertama dan terakhir, dan pilar-pilar di antaranya hanya boleh dibangun pada titik-titik kunci ini. Biaya jembatan adalah biaya pilar-pilarnya (sebanding dengan tingginya) ditambah biaya lengkungannya (sebanding dengan jumlah bahan yang digunakan). Jadi, jembatan dengan $k$ pilar setinggi $h_1,\ldots,h_k$, yang dipisahkan oleh jarak horizontal $d_1,\ldots,d_{k-1}$, memiliki biaya total

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

untuk konstanta $\alpha$ dan $\beta$ yang diberikan. ABC ingin membangun setiap jembatan dengan biaya serendah mungkin.

Masukan

Baris pertama masukan berisi empat bilangan bulat $n,h,\alpha,\beta$, dengan $n$ ($2\le n\le 10^4$) merupakan jumlah titik yang menjelaskan profil tanah, $h$ ($1\le h\le 10^5$) merupakan ketinggian jembatan yang diinginkan di atas permukaan laut, dan $\alpha,\beta$ ($1\le\alpha,\beta\le 10^4$) merupakan faktor biaya yang dijelaskan sebelumnya. Berikutnya terdapat $n$ baris, dengan baris ke-$i$ berisi dua bilangan bulat $x_i,y_i$ ($0\le x_1<x_2<\ldots<x_n\le 10^5$ dan $0\le y_i<h$), yang menjelaskan profil tanah.

Keluaran

Keluarkan biaya minimum untuk membangun jembatan dari posisi horizontal $x_1$ ke $x_n$ pada ketinggian $h$ di atas permukaan laut. Jika tidak mungkin membangun jembatan seperti itu, keluarkan impossible.

Contoh

Masukan 1

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

Keluaran 1

6460

Masukan 2

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

Keluaran 2

impossible