Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In some city, there are N towers called Tower 1 through Tower N and M traffic circles called Traffic Circle 1 through Traffic Circle M.
The town has the shape of a circle with a radius of 10^9 meters. Let (x, y) represent the point that is x meters east and y meters north of the center of the circle.
Tower i is at (\mathrm{PX}_i, \mathrm{PY}_i).
Traffic Circle i has the shape of a circle with a radius of R_i meters centered at (\mathrm{CX}_i, \mathrm{CY}_i) (not including the interior).
In this city, Takahashi will build some number of roads, each in the shape of a line segment, to satisfy the following conditions:

• Each endpoint of every road is a point at which one of the N towers stands or on one of the M traffic circles.
• It is possible to travel between every pair of towers in the following manner:
  • if you are now on some traffic circle, you can get to anywhere on that traffic circle;
  • if you are now at an endpoint of some road, you can get to the other endpoint of that road (but not to intermediate points);
  • no other type of movement is allowed.

Find the minimum possible total length of the roads built.

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
• (\mathrm{PX}_i, \mathrm{PY}_i) \neq (\mathrm{PX}_j, \mathrm{PY}_j) for i \neq j
• 0 \le \mathrm{CX}_i \le 1000
• 0 \le \mathrm{CY}_i \le 1000
• 1 \le R_i \le 1000
• (\mathrm{CX}_i, \mathrm{CY}_i, R_i) \neq (\mathrm{CX}_j, \mathrm{CY}_j, R_j) for i \neq j
• All values in input are integers.

Sample Input 1

2 1
0 0
6 0
3 0 2

Sample Output 1

2.00000000000

The towers and traffic circles are in the following positions:

We can satisfy the conditions by, for example, building the following two roads:

• a road in the shape of a line segment connecting (0, 0) and (1, 0);
• a road in the shape of a line segment connecting (5, 0) and (6, 0).

Here, the total length of the roads built is 2, which is the minimum possible sum.

Sample Input 2

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

Sample Output 2

2.12310562562

The towers and traffic circles are in the following positions:

It is optimal to build the following three roads:

• a road connecting (0, 1) and (0, 2);
• a road connecting (0, -2) and (0, -3);
• a road connecting (\frac{16 \sqrt{17}}{17}, 1 + \frac{4 \sqrt{17}}{17}) and (4, 2).

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

The towers and traffic circles are in the following positions: