Điều gì kết nối tất cả chúng ta? Thường thì đó là những cây cầu. Từ thời cổ đại, con người đã xây cầu cho đường bộ, tàu hỏa, người đi bộ, và xây cầu dẫn nước để vận chuyển nước. Đó là cách nhân loại không chịu khuất phục trước địa hình bất tiện.

Công ty Arch Bridges Construction (ABC) chuyên về — bạn đoán đúng rồi — xây cầu vòm. Kiểu cầu cổ điển này được đỡ bởi các trụ vươn lên từ mặt đất phía dưới cầu. Các vòm giữa những trụ phân bố trọng lượng cầu lên các trụ kề bên.

Một ví dụ về cầu vòm La Mã. Nguồn: Wikimedia Commons

Những cây cầu do ABC xây thường có khoảng cách giữa các trụ không đều nhau. Vì lý do thẩm mỹ, cầu của ABC luôn có các vòm hình bán nguyệt, như minh họa trong Hình B.1. Tuy nhiên, dù một vòm cầu có thể chạm đất, nó không được kéo dài xuống dưới mặt đất. Điều này khiến một số cách đặt trụ không thể thực hiện được.

(a) Hai trụ liên tiếp cách nhau $d$ được nối bằng một vòm bán nguyệt có bán kính $r=d/2$.

(b) Một cách đặt trụ không hợp lệ (vòm không được kéo dài xuống dưới mặt đất).

(c) Một cây cầu tương ứng với dữ liệu vào ví dụ 1.

Hình B.1: Các ví dụ về cầu.

Với biên dạng mặt đất và độ cao cầu mong muốn $h$, thường có nhiều cách xây cầu vòm. Ta mô hình hóa biên dạng mặt đất bằng một hàm tuyến tính từng đoạn được mô tả bởi $n$ điểm mốc $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$, trong đó tọa độ $x$ của một điểm là vị trí dọc theo cầu, còn tọa độ $y$ là độ cao mặt đất so với mực nước biển tại vị trí đó. Trụ đầu và trụ cuối phải được xây tại điểm mốc đầu và cuối, tương ứng; các trụ trung gian cũng chỉ có thể xây tại những điểm mốc này. Chi phí của một cây cầu là chi phí các trụ (tỉ lệ với chiều cao của chúng) cộng với chi phí các vòm (tỉ lệ với lượng vật liệu sử dụng). Do đó, một cây cầu có $k$ trụ với chiều cao $h_1,\ldots,h_k$, cách nhau những khoảng ngang $d_1,\ldots,d_{k-1}$, có tổng chi phí là

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

với $\alpha$ và $\beta$ là các hằng số cho trước. ABC muốn xây mỗi cây cầu với chi phí thấp nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên $n,h,\alpha,\beta$, trong đó $n$ ($2\le n\le 10^4$) là số điểm mô tả biên dạng mặt đất, $h$ ($1\le h\le 10^5$) là độ cao mong muốn của cầu so với mực nước biển, và $\alpha,\beta$ ($1\le\alpha,\beta\le 10^4$) là các hệ số chi phí đã mô tả ở trên. Tiếp theo là $n$ dòng, dòng thứ $i$ chứa hai số nguyên $x_i,y_i$ ($0\le x_1<x_2<\ldots<x_n\le 10^5$ và $0\le y_i<h$), mô tả biên dạng mặt đất.

Dữ liệu ra

In chi phí nhỏ nhất để xây cầu từ vị trí ngang $x_1$ đến $x_n$ ở độ cao $h$ so với mực nước biển. Nếu không thể xây được cây cầu nào như vậy, in impossible.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6460

Dữ liệu vào 2

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

Dữ liệu ra 2

impossible