Wi-Fi Setup

Farmer John's $N$ cows ($1 \le N \le 2000$) are standing at various positions along the straight path from the barn to the pasture, which we can think of as a one-dimensional number line. Because his cows like to stay in contact with each other, FJ wants to install Wi-Fi base stations at various positions so that all of the cows have wireless coverage.

The cost of a base station depends on the distance it can transmit (its power): a base station of power $r$ costs $A + B \cdot r$, where $A$ is a fixed cost for installing the station and $B$ is a cost per unit of transmission distance. If FJ installs such a device at position $x$, it can transmit to any cow located in the range $x - r$ through $x + r$. A base station with power $r = 0$ is allowed, but it only covers a cow located at exactly the same position as the transmitter.

Given the values of $A$ and $B$ as well as the locations of FJ's cows, determine the least expensive way FJ can provide wireless coverage for all of his cows.

• Line 1: Three space-separated integers $N$, $A$, and $B$ ($0 \le A, B \le 1000$).
• Lines 2 through $N+1$: Each line contains an integer in the range $0 \ldots 1{,}000{,}000$ giving the location of one of FJ's cows.

• Print the minimum cost of providing wireless coverage to all cows.
• The answer is always a multiple of $0.5$. If it is an integer, print it with no decimal part; otherwise print it followed by .5 (for example, 57.5).

Suppose there are 3 cows at positions $7$, $0$, and $100$, and a base station of power $r$ costs $20 + 5r$. The optimal solution is to build a base station at position $3.5$ with power $3.5$, covering the cows at positions $0$ and $7$, and another station at position $100$ with power $0$. The total cost is $(20 + 5 \cdot 3.5) + (20 + 5 \cdot 0) = 37.5 + 20 = 57.5$.