Problem L: RedBlue

Story

天空都市AIZUのUZIA高校では、競技プログラミングの部活動がとても盛んである。 この部活には、n人のRed Coderとn人のBlue Coderが所属している。

ある日の部活の時間に、Red CoderとBlue Coderでペアを組み、この部活からn組、KCPというコンテストに参加することとなった。この高校では、ペアを組む学生同士は握手するという習わしがあるので、部員たちは今すぐ自分のパートナーを見つけることにした。

部員たちは全速力で走るため、まっすぐにしか進めない。また、部員たちは、それぞれの部員が移動する距離の総和をできるだけ小さくしたいと思っている。

なお、部室には2つの円形のテーブルが置いてある。

Problem

二次元平面上に2つの円、n個の赤色の点、n個の青色の点がある。 2つの円の中心座標はそれぞれ(x₁, y₁), (x₂, y₂)であり、半径はそれぞれr₁, r₂である。 赤い点iは、座標(rx_i, ry_i)にあり、青い点jは、座標(bx_j, by_j)にある。

あなたは、以下の操作をn回繰り返す必要がある。
まだ選ばれていない点の中から、赤色の点と青色の点を１つずつ選んで、2点の共通の目的地を設定し、その目的地に向かって2点をそれぞれまっすぐ移動させる。 目的地は二次元平面上であれば、どこに設定しても構わない。ただし、選んだ2点は移動の際に円の内部を通過することはできないので、そのような移動が発生する目的地を設定することはできない。

n回の操作をしたときの移動距離の総和を最小化せよ。 n回の操作を行えない場合は、代わりに"Impossible" (""は除く) と出力せよ。

Input

入力は以下の形式で与えられる。

n
x1 y1 r1
x2 y2 r2
rx1 ry1
rx2 ry2
...
rxn ryn
bx1 by1
bx2 by2
...
bxn byn

入力は全て整数で与えられる。
1行目にnが与えられる。
2行目にx₁, y₁, r₁が空白区切りで与えられる。
3行目にx₂, y₂, r₂が空白区切りで与えられる。
4から3+n行に赤い点の座標(rx_i, ry_i)が空白区切りで与えられる。
4+nから3+2×n行に青い点の座標(bx_j, by_j)が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• 1 ≤ n ≤ 100
• -1000 ≤ x_i, y_i ≤ 1000
• 1 ≤ r_i ≤ 50
• -1000 ≤ rx_i, ry_i, bx_i, by_i ≤ 1000
• 同じ座標に複数の点が存在していることはない
• 任意の円の半径を絶対値10^-9以内で変化させても、高々絶対値10^-3しか変化しない
• 任意の円の半径を絶対値10^-9以内で変化させても、"Impossible"なケースは"Impossible"のままである
• 解は10000を超えない
• どの点も、円から10^-3以上離れていて、点が円周上に存在したり、点が円に内包されることはない
• 2つの円は共通面積を持たず、10^-3以上離れていることが保証される

Output

n回の操作をしたときの移動距離の総和の最小値を1行に出力せよ。なお、出力はジャッジ解の出力との絶対誤差が10^-2以内であれば許容される。
n回の操作を行えない場合は、代わりに"Impossible" (""は除く) と出力せよ。

Sample Input 1

2
3 3 2
8 3 2
0 3
3 7
8 0
8 7

Sample Output 1

13.8190642862

Sample Input 2

2
3 3 2
8 3 2
3 0
3 7
8 0
8 7

Sample Output 2

10.0000000000

Sample Input 3

2
3 3 2
8 3 2
0 0
0 5
11 0
11 5

Sample Output 3

22.0000000000

Sample Input 4

1
10 10 10
31 10 10
15 19
26 1

Sample Output 4

Impossible

点同士をつなぐことはできません。

Note

Link

 

---