Attacking Drones

Bytelandian air force has designed a new weapon system. It is similar to a drone but instead of shooting heat seeking missiles, it shoots energy beams at targets within its range on its way. The air force is about to conduct some tests, here is the test scenario:

You can consider the test ground to be a 2D plane. The targets are stationary, while the drones travel following a predefined line segment at a predefined speed, and can only shoot up to a predefined range. All the drones start at the same time, but they may travel at different speeds and shoot up to different ranges. The drones also have their own energy rating which is consumed when shooting the targets. The targets and drones are all considered to be points in the 2D plane.

The drones are automatically deactivated at the end of their respective paths. However there are some rules of engagement:

1. No two drones can shoot at the same target at the same time.
2. One drone can shoot at multiple targets if they are in range.
3. A drone can only shoot as long as it has energy left. For each target it shoots, it consumes 1 energy per second. The drone can start and stop shooting at a target at any time, or, it can even ignore a target.

For this problem, you will be given the coordinates of targets, the beginning and end coordinates for each drone along with the speed, range and energy rating. You have to find the maximum amount of energy used for shooting at the targets.

Please note, the energy is not consumed for the propulsion of the drone, there are separate energy storage which will ensure the full trajectory, so we don’t need to worry about that in this problem.

Input

The first line of input will be an integer T (T < 200), the number of test cases. For each test cases, first you will be given two integers N and M, where N (1 <= N <= 50) is the number of targets and M (1 <= M <= 50) is the number of drones. Each of the following N lines will contain a par of integers in the format X Y denoting the coordinate of each target. Finally, each of the next M lines will contain seven integers in the format SX SY EX EY S R E. Here, (SX, SY) and (EX, EY) are start and end coordinates of the drone, S, R, E are the drones speed, attack range and initial attack energy. All of the coordinates and S, R, E values will be between 1 and 1000 inclusive.

Output

For each test case, first print the case number starting from 1, then print the maximum amount of energy that was used for shooting the targets. Check sample input and output for details. Floating point errors less than 1e-5 will be ignored by the judge.

Sample

3
1 1
2 2
1 1 5 3 2 1 2
2 4
12 10
7 5
10 10 12 10 1 1 3
6 1 8 10 1 2 3
3 6 8 2 5 3 1
42 42 42 42 6 6 6
5 5
5 77
60 50
10 46
22 97
87 69
42 17 66 11 5 7 13
10 10 20 20 3 3 3
13 15 18 9 4 1 2
99 71 63 81 19 4 60
27 34 56 43 11 3 12

Case 1: 0.89442719
Case 2: 4.98377074
Case 3: 0.00000000