题目描述

是什么将你我连结？嗯，通常是桥梁。
自古以来，人们一直在为公路，铁路和行人而建造桥梁，就如同为了运输水而修建的引水渠一般。这是人类对不便的地理环境做出的回答。

拱桥建筑（Arch Bridges Construction，简称 ABC）致力于——你猜对了，建造拱桥。这一经典的桥梁结构由从桥下的地面中延伸出的柱子支撑。相邻柱子之间的拱形结构将桥面的重量分摊到柱子上。

由 ABC 建造的桥梁通常有间隔不同间距的柱子。出于美学原因，ABC 的桥梁总是有如图所示的半圆形拱门。然而，虽然桥拱可以接触地面，但它不能延伸到地面以下。这使得一些柱子的放置方案不可能实现。

给定地形剖面图和期望的桥高 $h$，通常有许多方法来建造拱桥。
我们将地面剖面模型化为由 $n$ 个关键点 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ 描述的分段线性函数，其中点的 $x$ 坐标是位置，$y$ 坐标是该位置的海拔高度。
必须在第一个和最后一个关键点处建造第一个和最后一个柱子，而且任何其他的柱子必须建造在这些关键点上。桥梁的花费为柱子的花费（与其高度成正比）加上拱的花费（与所用材料的量成正比）。所以一座拥有 $k$ 个高度分别为 $h_1, \ldots, h_k$ 的柱子，且水平间距分别为 $d_1, \ldots, d_{k-1}$ 的桥的总花费为：

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

其中常数 $\alpha, \beta$ 给定。ABC 想要知道建造每一座桥需要的最小花费。

输入格式

第一行包含四个整数 $n, h, \alpha, \beta$，$n$（$2 \le n \le 10^4$）为描述地形剖面图的点数，$h$（$1 \le h \le 10^5$）表示桥期望修建的海拔高度，而 $\alpha, \beta$（$1 \le \alpha, \beta \le 10^4$）为上面提到的花费因子。
接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i, y_i$（$0 \le x_1 < x_2 < \ldots < x_n \le 10^5$ 并且 $0 \le y_i < h$），描述地形剖面图。

输出格式

输出在海拔高度 $h$ 处从位置 $x_1$ 建造桥梁到 $x_n$ 的最低花费。
如果不可能建造出桥梁，输出 $\texttt{impossible}$。

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

6460

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

impossible

数据范围与提示

$2 \le n \le 10^4$

$1 \le h \le 10^5$

$1 \le \alpha, \beta \le 10^4$

$0 \le x_1 < x_2 < \ldots < x_n \le 10^5$

$0 \le y_i < h$

在不侵犯原题版权的情况下，本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，注明出处时需指向本题链接。