Warehouse Location Planning

Industrial engineering is largely about planning and improving industrial processes so that they run more efficiently, which means solving many optimization problems in areas such as product planning and supply management. Many of these problems are quite complex, but a clean, natural version of one central topic is easy to understand.

In the Warehouse Location Planning Problem, several stores need to be supplied with goods. To supply them, you may build one or more warehouses. Building a warehouse costs a certain amount that depends on where it is located. On the other hand, the farther a store is from the warehouse assigned to it, the more expensive it is to ship goods there. The warehouse locations therefore have to balance building costs against shipping costs, and the goal is to build warehouses so that the total cost is minimized.

We assume that, given the locations of a warehouse and a store, the shipping cost equals exactly their Euclidean distance. We also assume that a warehouse, once built, can supply arbitrarily many stores. You must always build at least one warehouse. The total cost is then the sum of the building costs, plus the sum over all stores of the shipping cost from each store to the warehouse it is assigned to.

The first line contains an integer $K \ge 1$, the number of data sets. Each data set has the following form:

• The first line of a data set contains two integers $n$ and $m$: the number of stores and the number of candidate warehouse locations. The number of stores satisfies $1 \le n \le 100$, and the number of candidate warehouse locations satisfies $1 \le m \le 20$.
• The next $n$ lines each describe one store by its $x$ and $y$ coordinates (real numbers).
• The next $m$ lines each describe one candidate warehouse location and its building price as real numbers $x$, $y$, $p$, where $p \ge 0$.

For each data set, first print Data Set x: on a line by itself, where $x$ is the data set number, starting from $1$. On the next line, print the minimum total cost at which all stores can be supplied, rounded to two decimal places.