Problem: Story

At UZIA High School in the sky city AIZU, the club activities of competitive programming are very active. N Red Coders and n Blue Coders belong to this club.

One day, during club activities, Red Coder and Blue Coder formed a pair, and from this club activity, n groups participated in a contest called KCP. At this high school, it is customary for paired students to shake hands, so the members decided to find their partner right away.

The members run at full speed, so they can only go straight. In addition, the members want to make the total distance traveled by each member as small as possible.

There are two circular tables in the club room.

Problem

There are two circles, n red dots, and n blue dots on a two-dimensional plane. The center coordinates of the two circles are (x1, y1) and (x2, y2), respectively, and the radii are r1 and r2, respectively. The red point i is at the coordinates (rxi, ryi) and the blue point j is at the coordinates (bxj, by j).

You need to repeat the following operation n times.
Select one red point and one blue point from the points that have not been selected yet, set two common destinations, and move each of the two points straight toward that destination. The destination may be set anywhere as long as it is on a two-dimensional plane. However, since the selected two points cannot pass through the inside of the circle when moving, it is not possible to set the destination where such movement occurs.

Minimize the total distance traveled after n operations. If you cannot perform n operations, output "Impossible" (excluding "") instead.

Constraints

The input satisfies the following conditions.

* 1 ≤ n ≤ 100
* -1000 ≤ xi, yi ≤ 1000
* 1 ≤ ri ≤ 50
* -1000 ≤ rxi, ryi, bxi, byi ≤ 1000
* There can never be more than one point at the same coordinates
* Even if the radius of any circle is changed within the absolute value of 10-9, only the absolute value of 10-3 changes at most.
* Even if the radius of any circle is changed within the absolute value of 10-9, the "Impossible" case remains "Impossible".
* The solution does not exceed 10000
* All points are more than 10-3 away from the circle, and the points are not on the circumference or contained in the circle.
* The two circles do not have a common area and are guaranteed to be at least 10-3 apart.

Input

The input is given in the following format.


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

All inputs are given as integers.
N is given on the first line.
The second line is given x1, y1, r1 separated by blanks.
On the third line, x2, y2, r2 are given, separated by blanks.
Lines 4 to 3 + n are given the coordinates of the red points (rxi, ryi) separated by blanks.
The coordinates of the blue points (bxj, byj) are given on the 3 + 2 × n lines from 4 + n, separated by blanks.

Output

Output the minimum value of the total distance traveled when n operations are performed on one line. The output is acceptable if the absolute error from the output of the judge solution is within 10-2.
If you cannot perform n operations, output "Impossible" (excluding "") instead.

Examples

Input

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


Output

13.8190642862


Input

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


Output

10.0000000000


Input

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


Output

22.0000000000


Input

1
10 10 10
31 10 10
15 19
26 1


Output

Impossible

Solution (in CPP):

Solution:
#include "bits/stdc++.h"

using namespace std;

using ld = double;
using Point = std::complex<ld>;

const ld eps = 1e-9, pi = acos(-1.0);

namespace std
{
bool operator<(const Point &lhs, const Point &rhs)
{
    if (lhs.real() < rhs.real() - eps)
        return true;
    if (lhs.real() > rhs.real() + eps)
        return false;
    return lhs.imag() < rhs.imag();
}
} // namespace std

Point input_point()
{
    ld x, y;
    std::cin >> x >> y;
    return Point(x, y);
}

bool eq(ld a, ld b)
{
    return (abs(a - b) < eps);
}

ld dot(Point a, Point b)
{
    return real(conj(a) * b);
}

ld cross(Point a, Point b)
{
    return imag(conj(a) * b);
}

// CCW::counter clockwise
int ccw(Point a, Point b, Point c)
{
    b -= a;
    c -= a;
    if (cross(b, c) > eps)
        return 1; // a,b,c : counter-clockwise
    if (cross(b, c) < -eps)
        return -1; // a,b,c : clockwise
    if (dot(b, c) < 0)
        return 2; // c,a,b : on a line
    if (norm(b) < norm(c))
        return -2; // a,b,c : on a line
    return 0;      // a,c,b : on a line
}

class Line
{
public:
    Point a, b;
    Line() : a(Point(0, 0)), b(Point(0, 0)) {}
    Line(Point a, Point b) : a(a), b(b) {}
};

ld dot(Line l, Line m)
{
    return dot((l.a - l.b), (m.a - m.b));
}

// l:line, m:line が交点を持つか
bool isis_ll(Line l, Line m)
{
    return !eq(cross(l.b - l.a, m.b - m.a), 0);
}

// l:line, s:segment
bool isis_ls(Line l, Line s)
{
    return isis_ll(l, s) &&
           (cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < eps);
}

// s:segment, t:segment
bool isis_ss(Line s, Line t)
{
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
           ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

// p が l:line 上に存在するか
bool isis_lp(Line l, Point p)
{
    return (abs(cross(l.b - p, l.a - p)) < eps);
}

bool isis_sp(Line s, Point p)
{
    return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}

// p から l に下ろした足との交点
Point proj(Line l, Point p)
{
    ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + t * (l.a - l.b);
}

// l:line, t:line の交点
Point is_ll(Line l, Line m)
{
    Point lv = l.b - l.a, mv = m.b - m.a;
    assert(cross(lv, mv) != 0);
    return l.a + lv * cross(mv, m.a - l.a) / cross(mv, lv);
}

// p, l:line の距離
ld dist_lp(Line l, Point p)
{
    return abs(p - proj(l, p));
}

ld dist_ll(Line l, Line m)
{
    return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}

ld dist_ls(Line l, Line s)
{
    return isis_ls(l, s) ? 0 : std::min(dist_lp(l, s.a), dist_lp(l, s.b));
}

ld dist_sp(Line s, Point p)
{
    Point r = proj(s, p);
    return isis_sp(s, r) ? abs(r - p) : std::min(abs(s.a - p), abs(s.b - p));
}

ld dist_ss(Line s, Line t)
{
    if (isis_ss(s, t))
        return 0;
    return std::min({dist_sp(s, t.a), dist_sp(s, t.b), dist_sp(t, s.a), dist_sp(t, s.b)});
}

class Circle
{
public:
    Point p;
    ld r;
    Circle() : p(Point(0, 0)), r(0) {}
    Circle(Point p, ld r) : p(p), r(r) {}
};

// c1, c2 の交点
std::vector<Point> is_cc(Circle c1, Circle c2)
{
    std::vector<Point> res;
    ld d = abs(c1.p - c2.p);
    ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
    ld dfr = c1.r * c1.r - rc * rc;
    if (abs(dfr) < eps)
        dfr = 0.0;
    else if (dfr < 0.0)
        return res; // no intersection
    ld rs = sqrt(dfr);
    Point diff = (c2.p - c1.p) / d;
    res.emplace_back(c1.p + diff * Point(rc, rs));
    if (dfr != 0.0)
        res.emplace_back(c1.p + diff * Point(rc, -rs));
    return res;
}

std::vector<Point> is_lc(Circle c, Line l)
{
    std::vector<Point> res;
    ld d = dist_lp(l, c.p);
    if (d < c.r + eps)
    {
        ld len = (d > c.r) ? 0.0 : sqrt(c.r * c.r - d * d); //safety;
        Point nor = (l.a - l.b) / abs(l.a - l.b);
        res.emplace_back(proj(l, c.p) + len * nor);
        res.emplace_back(proj(l, c.p) - len * nor);
    }
    return res;
}

std::vector<Point> is_sc(Circle c, Line l)
{
    std::vector<Point> v = is_lc(c, l), res;
    for (Point p : v)
        if (isis_sp(l, p))
            res.emplace_back(p);
    return res;
}

// p から c への接線
std::vector<Line> tangent_cp(Circle c, Point p)
{
    std::vector<Line> ret;
    Point v = c.p - p;
    ld d = abs(v);
    ld l = sqrt(norm(v) - c.r * c.r);
    if (isnan((long double)l))
    {
        return ret;
    }
    Point v1 = v * Point(l / d, c.r / d);
    Point v2 = v * Point(l / d, -c.r / d);
    ret.emplace_back(Line(p, p + v1));
    if (l < eps)
        return ret;
    ret.emplace_back(Line(p, p + v2));
    return ret;
}

bool isContain(Circle c, Line l)
{
    return dist_sp(l, c.p) + eps < c.r;
}

class minCostFlow
{
    using capacity_type = int;
    using cost_type = double;
    using pii = std::pair<cost_type, int>;
    const int INF = 1e9;
    struct Edge
    {
        int to, rev;
        capacity_type cap;
        cost_type cost;
        Edge(int to_, int _rev, capacity_type cap_, cost_type cost_)
            : to(to_), rev(_rev), cap(cap_), cost(cost_) {}
    };
    int V;
    std::vector<std::vector<Edge>> G;
    // ポテンシャル
    std::vector<cost_type> h;
    // 最短距離
    std::vector<cost_type> dist;
    // 直前の頂点, 辺
    std::vector<int> prevv, preve;

public:
    minCostFlow(int _V) : V(_V), G(_V), h(_V), dist(_V), prevv(_V), preve(_V) {}
    void add(int from, int to, capacity_type cap, cost_type cost)
    {
        G[from].push_back(Edge(to, G[to].size(), cap, cost));
        G[to].push_back(Edge(from, G[from].size() - 1, 0, -cost));
    }
    cost_type calc(int s, int t, int f)
    {
        cost_type res = 0;
        fill(h.begin(), h.end(), 0);
        while (f > 0)
        {
            std::priority_queue<pii, std::vector<pii>, std::greater<pii>> que;
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            que.push(pii(0, s));
            while (!que.empty())
            {
                pii p = que.top();
                que.pop();
                int v = p.second;
                if (dist[v] < p.first)
                    continue;
                for (size_t i = 0; i < G[v].size(); i++)
                {
                    Edge &e = G[v][i];
                    if (e.cap > eps && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to] + eps)
                    {
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        que.push(pii(dist[e.to], e.to));
                    }
                }
            }
            if (dist[t] == INF)
                return -1;
            for (int v = 0; v < V; v++)
                h[v] += dist[v];
            capacity_type d = f;
            for (int v = t; v != s; v = prevv[v])
            {
                d = std::min(d, G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = prevv[v])
            {
                Edge &e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    ld x1, y1, r1, x2, y2, r2;
    cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
    Circle c1(Point(x1, y1), r1), c2(Point(x2, y2), r2);
    vector<Point> rs, bs;
    for (int i = 0; i < n; i++)
    {
        rs.push_back(input_point());
    }
    for (int i = 0; i < n; i++)
    {
        bs.push_back(input_point());
    }
    // dist[i][j] := rs[i], bs[j] の最短移動距離
    vector<vector<ld>> dist(n, vector<ld>(n, 1e15));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            Line l = Line(rs[i], bs[j]);
            if (is_sc(c1, l).size() <= 1 && is_sc(c2, l).size() <= 1)
            {
                dist[i][j] = abs(rs[i] - bs[j]);
                continue;
            }
            // rs[i] から c1 への接線
            auto rl1 = tangent_cp(c1, rs[i]);
            // bs[j] から c1 への接線
            auto bl1 = tangent_cp(c1, bs[j]);
            // rs[i], c2 への接線
            auto rl2 = tangent_cp(c2, rs[i]);
            // bs[j], c2 への接線
            auto bl2 = tangent_cp(c2, bs[j]);
            for (auto l1 : rl1)
            {
                for (auto l2 : bl1)
                {
                    Point lv = l1.b - l1.a, mv = l2.b - l2.a;
                    if (cross(lv, mv) == 0)
                        continue;
                    Point p = is_ll(l1, l2);
                    if (isContain(c2, Line(rs[i], p)) || isContain(c2, Line(bs[j], p)))
                        continue;
                    dist[i][j] = min(dist[i][j], abs(p - rs[i]) + abs(p - bs[j]));
                }
            }
            for (auto l1 : rl2)
            {
                for (auto l2 : bl2)
                {
                    Point lv = l1.b - l1.a, mv = l2.b - l2.a;
                    if (cross(lv, mv) == 0)
                        continue;
                    Point p = is_ll(l1, l2);
                    if (isContain(c1, Line(rs[i], p)) || isContain(c1, Line(bs[j], p)))
                        continue;
                    dist[i][j] = min(dist[i][j], abs(p - rs[i]) + abs(p - bs[j]));
                }
            }
            // rs[i]-c1, bs[j]-c2
            for (auto l1 : rl1)
            {
                for (auto l2 : bl2)
                {
                    Point lv = l1.b - l1.a, mv = l2.b - l2.a;
                    if (cross(lv, mv) == 0)
                        continue;
                    Point p = is_ll(l1, l2);
                    if (isContain(c2, Line(rs[i], p)) || isContain(c1, Line(bs[j], p)))
                        continue;
                    dist[i][j] = min(dist[i][j], abs(p - rs[i]) + abs(p - bs[j]));
                }
            }
            // rs[i]-c2, bs[j]-c1
            for (auto l1 : rl2)
            {
                for (auto l2 : bl1)
                {
                    Point lv = l1.b - l1.a, mv = l2.b - l2.a;
                    if (cross(lv, mv) == 0)
                        continue;
                    Point p = is_ll(l1, l2);
                    if (isContain(c1, Line(rs[i], p)) || isContain(c2, Line(bs[j], p)))
                        continue;
                    dist[i][j] = min(dist[i][j], abs(p - rs[i]) + abs(p - bs[j]));
                }
            }
        }
    }
    minCostFlow mcf(2 * n + 2);
    for (int i = 0; i < n; i++)
    {
        mcf.add(0, i + 1, 1, 0);
        mcf.add(n + i + 1, 2 * n + 1, 1, 0);
        for (int j = 0; j < n; j++)
        {
            int st = i + 1, gt = n + 1 + j;
            if (dist[i][j] != 1e15)
            {
                mcf.add(st, gt, 1, dist[i][j]);
            }
        }
    }
    auto ret = mcf.calc(0, 2 * n + 1, n);
    if (ret == -1)
        cout << "Impossible" << endl;
    else
        cout << fixed << setprecision(10) << ret << endl;
}