Zebra Herd

Zebras are highly social animals. Like other members of the horse family, they form groups that tend to stay together and spend time with one another fairly regularly, though not exclusively. Researchers want to understand how communities of zebras evolve over time and what triggers those changes. All they have to work with are observations of where the zebras are at various moments in time, and from those they would like to recover the most natural groupings.

The working assumptions are:

• (a) if a zebra belongs to a group, it tends to stay close to the other members of that group;
• (b) if a zebra does not belong to a group, it tends to stay farther from the members of that group;
• (c) a zebra rarely changes its group membership.

Let us make this precise. You are given a sequence of observations. At each observation time you know the exact location of every zebra, and the distance between two zebras is their Euclidean (straight-line) distance. Assume the herd splits into exactly two groups, which we denote by two colors. For every time step we color each zebra either red or blue to indicate which group it belongs to.

To model assumption (c), we charge a penalty of $c$ every time a single zebra changes its color between two consecutive time steps. To model assumptions (a) and (b), at each time step we look at the distance $d(i, j)$ between every pair of zebras $i$ and $j$: if $i$ and $j$ have the same color we charge a penalty of $a \cdot d(i, j)$ for that pair, and if they have opposite colors we charge a penalty of $-b \cdot d(i, j)$ (that is, a bonus).

Given a coloring of all zebras for every time step, the total penalty is the sum of all pair penalties over all time steps plus all color-change penalties. Your task is to find the smallest total penalty achievable by any coloring. You only need to output this minimum total penalty, not the coloring itself.

The first line contains the number $K$ of data sets. Each of the $K$ data sets has the following form.

The first line of a data set contains two integers $z$ and $t$: the number of zebras $2 \le z \le 10$ and the number of time steps $2 \le t \le 50$. The next line contains three non-negative floating-point numbers $a$, $b$, and $c$, the penalty multipliers. Then follow $t$ lines describing the zebra positions. Each of these lines contains $2z$ floating-point numbers giving the positions as $x_1\ y_1\ x_2\ y_2\ \dots\ x_z\ y_z$. The first such line gives the positions at time $1$, the second at time $2$, and so on.

For each data set, print a line Data Set x: where $x$ is the data set's number (starting from $1$). On the following line, print the minimum total penalty that any coloring over time can achieve, rounded to exactly two decimals. Separate consecutive data sets with a single blank line.