Problem Description

On a two-dimensional coordinate plane, there are $ N $ large towers and $ M $ small towers. The coordinates of the $ i $-th large tower $(1 \leq i \leq N)$ are $ (x_i, y_i) $, and its color is $ c_i $. The coordinates of the $ i $-th small tower $(1 \leq i \leq M)$ are $ (X_i, Y_i) $, and its color is $ C_i $. Here, the color of the towers is given as an integer, where $ 1, 2, 3 $ represent red, green, and blue, respectively. Note that multiple towers may exist at the same coordinates.

You want to build several bridges connecting pairs of towers such that any large tower can reach any other large tower by crossing several bridges. (Small towers can be treated in any way.)

The construction cost of a bridge connecting towers of the same color is equal to the Euclidean distance between the two towers, and the construction cost of a bridge connecting towers of different colors is ten times that distance. (The size of the towers does not affect the construction cost, and intersections of bridges are not considered.)

Find the minimum total cost required to achieve this goal.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ x_1 $ $ y_1 $ $ c_1 $ $ x_2 $ $ y_2 $ $ c_2 $ $ : $ $ x_N $ $ y_N $ $ c_N $ $ X_1 $ $ Y_1 $ $ C_1 $ $ X_2 $ $ Y_2 $ $ C_2 $ $ : $ $ X_M $ $ Y_M $ $ C_M $

Output Format

Output a real number representing the minimum total cost required to achieve the goal. The answer will be judged correct if the absolute or relative error with the judge's output is within $ 10^{-6} $.

Sample Input and Output

Sample Input #1

3 1
0 0 1
0 1 1
1 0 1
1 1 1

Sample Output #1

2.000000000000

Sample Input #2

3 1
0 10 1
10 0 2
10 20 3
10 10 1

Sample Output #2

210.000000000000

Notes/Hints

Constraints

• $2 \leq N \leq 30$
• $1 \leq M \leq 5$
• $0 \leq x_i, y_i \leq 1,000$
• $0 \leq X_i, Y_i \leq 1,000$
• $1 \leq c_i, C_i \leq 3$
• All values in the input are integers.

Sample Explanation 1

The first large tower should be connected directly to the second and third large towers. The total cost is $ 1 + 1 = 2 $.

Sample Explanation 2

Each small tower should be connected to the respective large towers. The total cost is $10 + 10 \times 10 + 10 \times 10 = 210$.

见题面 Input 部分

见题面 Output 部分