Minimum Cost Wifi Coverage

Farmer John has N cows standing along a one-dimensional number line. He wants to install Wifi base stations such that every cow receives wireless coverage. A base station installed at position \(x\) with transmission power \(r\) costs \(A + B \times r\) and covers the interval \([x - r, \; x + r]\). Even a base station with \(r = 0\) is allowed (covering only the exact location where it is installed).

Given the cost parameters \(A\) and \(B\) and the positions of the cows, determine the minimum total cost required to cover all the cows.

Note: For any contiguous group of cows with positions \(p_i, p_{i+1}, \dots, p_j\) (after sorting), the optimal strategy is to place the base station at \(x = \frac{p_i + p_j}{2}\) which requires a transmission power of \(r = \frac{p_j - p_i}{2}\), and thus incurs a cost of \(A + B \times \frac{p_j - p_i}{2}\).

inputFormat

The first line contains three integers: N (\(1 \le N \le 2000\)), A, and B, where A is the fixed installation cost and B is the cost per unit of transmission distance. The next line contains N space-separated integers representing the positions of the cows on the number line.

outputFormat

Output a single floating point number: the minimum total cost to cover all cows, printed with exactly one decimal place.

sample

1 10 5
7

10.0