Attack of the Giant n-pus#3115
A pirate ship is attacked by a giant -pus^{1}. The tentacles and the head of the creature have pierced the deck and are causing chaos on the ship. In an attempt to stop the creature from completely destroying the ship, the captain charges towards its head. Unfortunately, he is quickly knocked back by one of the tentacles. The captain realizes he cannot attack the head of the -pus as long as it can move its tentacles freely.
Luckily, the captain is not alone on the ship. There are pirates (p \geq n) on the deck, ready to follow the captain's orders. The captain devises the following plan: If each tentacle is attacked by one pirate, he can freely reach the head of the creature and finish it off. For safety, the captain will only start moving after each tentacle is attacked by a pirate. When the captain reaches the head, he can instantly kill the creature. The captain wants to determine which pirates should be sent to which tentacles to kill the creature as quickly as possible. Since this situation arises regularly, the captain asks you to write a program to solve this problem.
____________ ^{1} An -pus is like an octopus, but with tentacles.
The first line contains the number of test cases.
Each test case consists of:
One line with two integers and (1 \leq n \leq p \leq 100): the number of tentacles of the -pus and the number of pirates (excluding the captain).
One line with three integers x_c, y_c, and v_c: the coordinates and speed of the captain.
lines, each with three integers x_i, y_i, and v_i: the coordinates and speed of each pirate.
One line with two integers x_h and y_h: the coordinates of the head of the -pus.
lines, each with two integers x_j and y_j: the coordinates of each tentacle.
All coordinates satisfy 0 \leq x, y \leq 10000. All speeds satisfy 1 \leq v \leq 100.
The captain, pirates, head, and tentacles are all considered to be point-like (i.e., they have no size). All positions are distinct.
The captain and all pirates move to their targets in straight lines at their respective speeds, unhindered by anyone or anything.
For each test case, output one real number on a single line: the minimum time for the captain to kill the -pus. The answer should have an absolute or relative error of at most 10^{-6}.
Example 1