URI Online Judge | 1413

Hurry Up!

By Rodrigo Schmidt Brazil
Timelimit: 3

Orienteering, a cross-country race on foot where competitors receive a map and a compass, is a sport very popular in some european countries. Johnny and his friends entered an orienteering competition and intend to win it.

In this competition, each team member wears a different color and starts from a different place.  There are some finishing points, each one with a list of colors it "accepts".  Every competitor in a team must go from its starting place to one of the finishing places which accept its color.  No team member can go to the same finishing place of another member. The team penalty in the game is the sum of the time team members take from their starting to their final places.

To maximize the chances of winning, Johnny and his team members want to determine the most appropriate finishing point for each member of the team, assuming he and his friends advance at possibly different speeds. That is, they want to determine for each team member one different finishing point, so that the total time penalty for the team will be minimized.

You may assume that there will always be an answer (a different finishing point for each team member).


Your program should process several test cases. The first line of a test case contains two integers N and M, representing respectively the number of players in the team and the number of existing finishing points (1 ≤ NM ≤ 100). The next N lines contain each two integers X and Y representing the starting position of a player (-20000 ≤ X, Y ≤ 20000) and a real s, representing the player’s speed. Players are identified by the order their starting position appear on the input (the first to appear is number 1, the second is number 2, and so on).  These identification numbers are also used to represent the players colors.  The following M lines contain each two integers X and Y defining the position of a finishing point (-20000 ≤ X, Y ≤ 20000) and a list of colors Ci accepted by that finishing point (1 ≤ CiN ); the end of the list is indicated by a value of 0 (zero). The end of input is indicated by N = M = 0.


For each test case, your program should output a single line, containing a real value representing the minimal time penalty, i.e. the minimal sum of time taken by the players to reach their respective finishing points. Your answers must be rounded to one digit after the decimal point.

Sample Input Sample Output

1 1
0 0 1.0
1 1 1 0
2 3
100 100 1.0
100 200 1.0
110 100 1 2 0
110 200 1 2 0
200 250 1 0
1 2
0 0 1.0
11111 11111 1 0
11111 -11111 1 0
0 0