Problem H

We are constructing a new communication network in our city! Thanks to the new technology, which provides us with a more effective way to communicate between people from different places. However, we should still make a budget before the construction starts.

Totally there are $N$ buildings in the city, each located at some $(x_i, y_i)$ on a two-dimensional map. In order to satisfy users from all buildings, we are going to choose some of the buildings and set up network stations on their roofs. A station can serve a circle-shaped area around the building itself, and we can control its power to change the radiation radius $r$. For example, if we set up a station at building $(x_s, y_s)$ with radius $r$, then it serves all buildings no further than $r$ from $(x_s, y_s)$.

The cost differs if we choose different buildings and radius. It costs $C_s$ to construct a station, and $C_r \cdot r$ to set it up with radius $r$. We can choose different radius for different stations. What's the minimum cost if all buildings are covered by at least one station?

The number of test cases $T (T \leq 10)$ will occur in the first line of input.

For each test case:

The first line contains the number of buildings $N (1 \leq N \leq 8)$ and two integers $C_s, C_r (1 \leq C_s, C_r \leq 1000)$.

Each of the following $N$ lines contains the coordinate of the $i$th building $(x_i, y_i)$. The coordinates are integers and their absolute values don't exceed 10^3.

For each test case, output the minimum cost to cover all buildings, rounded in 2 decimals.

2
2 1 1
0 0
4 4
3 100 1
0 0
1 1
500 500

2.00
201.41

In the first sample, the optimal way is to set up a station on each building with r = 0.

In the second sample, the optimal way is to set up a station on either of the first two buildings with r = sqrt(2) and another one with r = 0 on the third building.

校第十六届大学生程序设计竞赛暨2016省赛集训队选拔赛