题目背景

Warning: If you submit a malicious program, you will be banned.

警告：恶意提交本题将被封号。

题目描述

What connects us all? Well, it is often bridges. Since ancient times, people have been building bridges for roads, for trains, for pedestrians, and as aqueducts to transport water. It is humanity's way of not taking inconvenient geography for an answer.

The company Arch Bridges Construction (ABC) specializes in—you guessed it—the construction of arch bridges. This classical style of bridge is supported by pillars that extend from the ground below the bridge. Arches between pillars distribute the bridge's weight onto the adjacent pillars.

The bridges built by ABC often have pillars spaced at irregular intervals. For aesthetic reasons, ABC's bridges always have semicircular arches, as illustrated in Figure B.1. However, while a bridge arch can touch the ground, it cannot extend below the ground. This makes some pillar placements impossible.

Given a ground profile and a desired bridge height $h$, there are usually many ways of building an arch bridge. We model the ground profile as a piecewise-linear function described by $n$ key points $(x_1, y_1),(x_2, y_2), \dots ,(x_n, y_n)$, where the $x-\text{coordinate}$ of a point is the position along the bridge, and the $y-\text{coordinate}$ is the elevation of the ground above sea level at this position along the bridge. The first and last pillars must be built at the first and last key points, and any intermediate pillars can be built only at these key points. The cost of a bridge is the cost of its pillars (which is proportional to their heights) plus the cost of its arches (which is proportional to the amount of material used). So a bridge with $k$ pillars of heights $h_1, \dots , h_k$ that are separated by horizontal distances $d_1, \dots , d_{k - 1}$ has a total cost of

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

for some given constants $\alpha$ and $\beta$. ABC wants to construct each bridge at the lowest possible cost.

输入格式

The first line of input contains four integers $n, h, \alpha, and \beta$, where $n$ ($2 \leq n \leq 10^4$) is the number of points describing the ground profile, $h$ ($1 \leq h \leq 10^5$) is the desired height of the bridge above sea level, and $\alpha, \beta$ ($1 \leq \alpha, \beta \leq 10^4$) are the cost factors as described earlier. Then follow $n$ lines, the $i^{\text{th}}$ of which contains two integers $x_i, y_i$ ($0 \leq x_1 < x_2 < . . . < x_n \leq 10^5$ and $0 \leq yi < h$), describing the ground profile.

输出格式

Output the minimum cost of building a bridge from horizontal position $x_1$ to $x_n$ at height $h$ above sea level. If it is impossible to build any such bridge, output impossible.

题目大意

给定一个地形剖面图，用 $n$（$n≤10^4$）个点描述，点 $i$ 和点 $i+1$ 之间有直线连接的地面。

你需要建一座拱桥，连接点 $1$ 和点 $n$，桥面的高度为 $h$。

你可以在桥中间建若干个柱子，以分配重量，柱子只能恰好建在给出的 $n$ 个点上（点 $1$ 和点 $n$ 上必须有柱子）。

相邻的两根柱子之间需要建一个半圆形的拱，准确地说，拱的半径为两根柱子之间的距离的一半，并且与两根柱子和桥面相切。

拱可以与地面相切，但不能相交。

同时，桥的花费与柱子高度和拱面积有关，具体地，给出两个参数 $α$ 和 $β$，则花费为：

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

其中 $k$ 为柱子数量，$h_i$ 为第 $i$ 个柱子的高度，$d_i$ 为第 $i$ 个柱子到第 $i+1$ 个柱子的距离。

问是否可以建出桥，若可以，问最小花费，否则输出 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

提示

Source: ICPC 2019 World Finals.