Problem Description

In a certain city, there are $ N $ towers numbered from $ 1 $ to $ N $ and $ M $ roundabouts numbered from $ 1 $ to $ M $.
The city is shaped like a circle with a radius of $ 10^9 $ meters. The center of this circle is considered the origin, and a point $ x $ meters east and $ y $ meters north from this origin is denoted as point $ (x, y) $.
Tower $ i $ is located at point $(\mathrm{PX}_i, \mathrm{PY}_i)$.
Roundabout $ i $ is a circle (excluding the interior) with a radius of $ R_i $ meters centered at point $(\mathrm{CX}_i, \mathrm{CY}_i)$.
Takahashi wants to add several linear roads to this city such that the following conditions are met:

• The endpoints of the added roads must either coincide with one of the $ N $ tower locations or lie on one of the $ M $ roundabouts.
• According to the following rules, any two tower locations must be mutually accessible:
• If the current location is on a roundabout, it can move to any point on that roundabout.
• If the current location is an endpoint of a road, it can move to the other endpoint of that road (note that movement is restricted to endpoints only).
• No other movements are allowed.

Find the minimum possible total length of the added roads.

Input Format

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

$ N $ $ M $ $\mathrm{PX}_1$ $\mathrm{PY}_1$ $\mathrm{PX}_2$ $\mathrm{PY}_2$ $\mathrm{PX}_3$ $\mathrm{PY}_3$ $\hspace{22pt} \vdots$ $\mathrm{PX}_N$ $\mathrm{PY}_N$ $\mathrm{CX}_1$ $\mathrm{CY}_1$ $ R_1 $ $\mathrm{CX}_2$ $\mathrm{CY}_2$ $ R_2 $ $\mathrm{CX}_3$ $\mathrm{CY}_3$ $ R_3 $ $\hspace{33pt} \vdots$ $\mathrm{CX}_M$ $\mathrm{CY}_M$ $ R_M $

Output Format

Output the answer.
The answer will be considered correct if the absolute or relative error is at most $ 10^{-5} $.

Sample Input and Output

Sample Input #1

2 1
0 0
6 0
3 0 2

Sample Output #1

2.00000000000

Sample Input #2

2 2
4 2
0 1
0 0 2
0 1 4

Sample Output #2

2.12310562562

Sample Input #3

3 4
9 2
5 20
0 21
0 0 2
0 0 10
16 0 10
10 15 3

Sample Output #3

13.10603728957

Notes/Hints

Note

Discussion of this problem is prohibited until 2021/4/24 18:00 JST. Any mention may result in a claim for damages. It is acceptable to publish the total score or certification level after the exam, but please refrain from disseminating information about which problems were solved.

Constraints

• $2 \le N \le 50$
• $1 \le M \le 8$
• $0 \le \mathrm{PX}_i \le 1000$
• $0 \le \mathrm{PY}_i \le 1000$
• If $i \neq j$, then $(\mathrm{PX}_i, \mathrm{PY}_i) \neq (\mathrm{PX}_j, \mathrm{PY}_j)$
• $0 \le \mathrm{CX}_i \le 1000$
• $0 \le \mathrm{CY}_i \le 1000$
• $1 \le R_i \le 1000$
• If $i \neq j$, then $(\mathrm{CX}_i, \mathrm{CY}_i, R_i) \neq (\mathrm{CX}_j, \mathrm{CY}_j, R_j)$
• All values in the input are integers.

Sample Explanation 1

The arrangement of each tower and roundabout is as shown in the figure below. Adding the following three roads is the optimal method: - A linear road connecting $ (0, 1) $ and $ (0, 2) $ - A linear road connecting $ (0, -2) $ and $ (0, -3) $ - A linear road connecting $(\frac{16 \sqrt{17}}{17}, 1 + \frac{4 \sqrt{17}}{17})$ and $ (4, 2) $

Sample Explanation 3

The arrangement of each tower and roundabout is as shown in the figure below. 

见题面 Input 部分

见题面 Output 部分