Problem D
Bouquet

Gustav’s panda Ivar is in the middle of a flower field. He knows that his best friend Mango loves flowers, so he wants to give her a nice bouquet with one red, one green and one blue flower. Ivar just filled his stomach with bamboo, so he doesn’t want to walk too far. He’s currently at the coordinate $(0,0)$. What’s the shortest euclidean distance he has to walk in order to pick one flower of each color and return to $(0,0)$?

Input

The first line of input contains the integer $N$ ($3 \leq N \leq 6\, 000$), the number of flowers on the field.

The following $N$ lines each contain two integers $x$ and $y$ ($-10^9 \leq x,y \leq 10^9$) and one character $c$ indicating the color of the flower, R, G or B.

It is guaranteed that there is at least one flower of each color and that no two flowers have the same coordinates.

Output

Output a decimal number, the shortest euclidean distance Ivar has to walk.

Your answer will be considered correct if the absolute or relative difference from the correct answer is less than $10^{-5}$.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample 1

An optimal order is to first pick the green flower, then the blue flower, then the first red flower, and finally return to the origin.

Explanation of Sample 2

An optimal order is to first pick the blue flower, then the first red flower, then the first green flower, and finally return to the origin.

4
2 3 B
-1 0 G
3 3 R
-3 3 R

10.485281374238570

5
-1 0 B
-3 0 R
2 3 R
1 1 G
-3 3 G

8.537319187990756