Basketball rebound placement

Given opposing and candidate positions plus rebound spot probabilities, choose 5 of n candidate spots to maximize expected points from the resulting fast-break race.

Medium6Brute forceCombinatoricsGeometrySimulationNo attempts yetTime limit2sMemory limit512 MB

Problem

The court is a rectangle whose opposite corners are (0.0,0.0)(0.0, 0.0) and (94.0,50.0)(94.0, 50.0), measured in feet. Your team defends the basket at (0.0,25.0)(0.0, 25.0) and attacks the basket at (94.0,25.0)(94.0, 25.0).

When a shot misses, the ball bounces off the rim and lands somewhere on the court. You know mm possible landing spots and the probability that the ball goes to each one. The five opposing players stand at fixed positions. Your team picks 5 of nn candidate positions and puts one player on each of them.

Once the ball lands on a spot, the player closest to that spot among all 10 players on the court picks it up. That player runs in a straight line to the spot, takes the ball, then runs in a straight line to the basket that the player's own team attacks. At the same moment, the five players of the other team run in a straight line to the basket that their own team defends. Every player runs at 20 feet per second.

Let tt be the number of seconds by which the player with the ball reaches the basket ahead of the fastest defender. If a defender arrives first, tt is negative. The probability of scoring is 12(t+1)1 - 2^{-(t+1)} when t0t \ge 0 and 2t12^{t-1} when t<0t < 0. A made basket is worth 2 points.

A basket by your team counts as +2+2 points and a basket by the other team counts as 2-2 points. Choose the 5 candidate positions that maximize the expected number of points, and report that expected value.

Input

The first line contains the number of data sets KK, with 1K201 \le K \le 20. KK data sets follow.

The first line of a data set contains two integers nn and mm. nn is the number of candidate positions for your players, with 5n155 \le n \le 15, and mm is the number of possible landing spots, with 1m1001 \le m \le 100.

The next line contains 10 real numbers x1,y1,,x5,y5x^-_1, y^-_1, \dots, x^-_5, y^-_5, the positions of the five opposing players. The next line contains 2n2n real numbers xj+,yj+x^+_j, y^+_j, the candidate positions for your players. The last line contains 3m3m real numbers forming mm triples (xk,yk,pk)(x^\circ_k, y^\circ_k, p_k). The first two values of a triple are the coordinates of the kk-th landing spot, and pkp_k is the probability that the ball goes there.

Every xx coordinate is between 0 and 94, and every yy coordinate is between 0 and 50. Each pkp_k is between 0 and 1, and kpk=1\sum_k p_k = 1. Whichever landing spot you take, no two of the 5 opposing positions and the nn candidate positions have distances to it that differ by less than 0.0010.001, so the player who picks the ball up is always unique.

Output

For each data set, print Data Set x: on a line by itself, where x is the number of the data set counting from 1. On the next line, print the maximum expected number of points, rounded to two decimal places. Print one blank line after each data set.

If the rounded value is zero, print 0.00 and not -0.00. The exact answer is farther than 10610^{-6} from any midpoint between two values with two decimal places.