The Hare and the Hedgehogs

Germany has a famous fable about a hare and a hedgehog. The hare keeps bragging about how fast he is, so the hare and the hedgehog agree to a race across a field. The instant the race begins the hare sprints off, but when he reaches the far end the hedgehog is already there. He dashes back even faster, yet the hedgehog is waiting there too. He runs back and forth faster and faster, meeting the hedgehog at the opposite end every time, until he finally collapses. Of course the hedgehog won, because the one waiting at the far end was actually his wife. When the story is told to children the moral is usually taken to be either that boasting invites humiliation, or that teamwork is powerful. Unfortunately, the lesson the story really teaches is that it is easy to win if you cheat.

Here we consider a more elaborate race between one hare and several hedgehogs. The hare's course is made of several straight legs, given by a sequence of points $(x_1, y_1), \dots, (x_n, y_n)$ in the plane. The race starts at the origin $(0, 0)$. The hare runs at a constant speed $u$ in a straight line to $(x_1, y_1)$, then in a straight line to $(x_2, y_2)$, and so on to $(x_n, y_n)$.

The hedgehogs move at a (possibly different) speed $v$ and may walk anywhere they like. Scoring works as follows. At the exact moment the hare reaches $(x_i, y_i)$ ($1 \le i \le n$), if at least one hedgehog is standing on $(x_i, y_i)$, the hedgehogs win that leg; otherwise the hare wins it. If a hedgehog and the hare reach the point at exactly the same time, the hare wins the leg. Compute the largest number of legs the hedgehogs can win as a team.

The first line contains the number $K$ of data sets. It is followed by $K$ data sets, each of the following form.

The first line of a data set contains two integers $n$, $h$ and two floating-point numbers $u$, $v$. Here $1 \le n \le 10$ is the number of legs to be run, $1 \le h \le 5$ is the number of hedgehogs on the field, $u$ is the hare's speed, and $v$ is the hedgehogs' speed, both in m/s.

This is followed by $n$ lines, each giving the coordinates of a point $(x_i, y_i)$ as two floating-point numbers. This is followed by $h - 1$ lines, each giving the initial coordinates $(x'_i, y'_i)$ of hedgehog $i = 2, \dots, h$. Hedgehog $1$ always starts at the origin. All coordinates are in meters.

For each data set, first output a line "Data Set x:", where x is its number (starting from 1). On the next line, output the maximum number of legs the hedgehogs can win together. Print one blank line between consecutive data sets.