Optimal Arch Bridge Construction

Arch Bridges Construction (ABC) specializes in building arch bridges. The ground profile is given by n key points \((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\) where x_i is the horizontal coordinate and y_i is the ground elevation. The bridge deck must be built at a fixed elevation \(h\) (i.e. the top of every pillar is at height \(h\) above sea level). Consequently, if a pillar is built at key point \((x_i, y_i)\), its height will be \(h - y_i\) (and it is required that \(h \ge y_i\)). Note that the first and last key points are mandatory pillars.

Between every two consecutive pillars built at \(x_i\) and \(x_j\) (with \(x_i < x_j\)), a semicircular arch is constructed that connects the top of the pillars. Since the endpoints are at the same elevation \(h\), the arch is modeled as the lower half of a circle with diameter \(d = x_j - x_i\). Its equation is given in LaTeX format by $$y(x) = h - \sqrt{\left(\frac{d}{2}\right)^2 - \left(x - \Bigl(x_i+\frac{d}{2}\Bigr)\right)^2}, \quad x\in [x_i,x_j].$$

For the bridge to be feasible, the arch must not extend below the ground. That is, for every key point \((x_k, y_k)\) between \(x_i\) and \(x_j\) (inclusive), the following condition must hold: $$h - \sqrt{\left(\frac{d}{2}\right)^2-\left(x_k-\Bigl(x_i+\frac{d}{2}\Bigr)\right)^2}\ge y_k.$$

The total cost of the bridge is defined as $$\alpha \cdot \sum_{\text{pillars}} (h - y) + \beta \cdot \sum_{\text{arches}} d^2,$$ where \(\alpha\) and \(\beta\) are given constants. Since the pillar cost depends on the pillar heights and the arch cost depends on the square of the horizontal distance between pillars, there is a trade-off between using many pillars and fewer, longer arches. Your task is to choose a subset of key points (the first and last must be chosen) so that feasible arches can be built between consecutive pillars and the total cost is minimized. Output the minimum total cost.

inputFormat

The input consists of the following:

• An integer n (\(2 \le n \le 1000\)) representing the number of key points.
• A line containing three numbers: h (bridge deck elevation), alpha (pillar cost coefficient), and beta (arch cost coefficient). It is guaranteed that \(h \ge y_i\) for all key points.
• n lines follow, each containing two numbers: x and y, representing the horizontal coordinate and ground elevation of a key point. The x coordinates are strictly increasing.

outputFormat

Output a single number: the minimum total cost to construct a feasible bridge. The answer will be accepted if it has an absolute or relative error of at most \(10^{-6}\).

sample

4
10 1 1
0 2
3 3
6 2
10 0

67.000000