Problem: A root tree is a directed acyclic graph that contains one node (root), from which there is exactly one path to any other node.

A root tree is binary if each node has at most two outgoing arcs.

When a binary tree is painted on the plane, all arcs should be directed from top to bottom. That is, each arc going from u to v must meet the condition yu > yv.

You've been given the coordinates of all tree nodes. Your task is to connect these nodes by arcs so as to get the binary root tree and make the total length of the arcs minimum. All arcs of the built tree must be directed from top to bottom.

Input

The first line contains a single integer n (2 ≤ n ≤ 400) — the number of nodes in the tree. Then follow n lines, two integers per line: xi, yi (|xi|, |yi| ≤ 103) — coordinates of the nodes. It is guaranteed that all points are distinct.

Output

If it is impossible to build a binary root tree on the given points, print "-1". Otherwise, print a single real number — the total length of the arcs in the minimum binary tree. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6. 

Examples

Input

3
0 0
1 0
2 1


Output

3.650281539872885


Input

4
0 0
1 0
2 1
2 0


Output

-1

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author emotionalBlind
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        LatticePoint[] points = new LatticePoint[n];

        for (int i = 0; i < n; ++i) {
            int x = in.readInt();
            int y = in.readInt();
            points[i] = new LatticePoint(x, y);
        }

        MCMF2Double network = new MCMF2Double(2 * n + 2);

        int source = 2 * n;
        int sink = source + 1;
        for (int i = 0; i < n; ++i) {
            network.add(source, i, 2, 0);
            network.add(i + n, sink, 1, 0);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (points[i].getY() > points[j].getY()) {
                    network.add(i, j + n, 1, points[i].dist(points[j]));
                }
            }
        }
        network.run(source, sink);
        if (network.getFlow() < n - 1) {
            out.printLine(-1);
        } else {
            out.printLine(network.getMinCost());
        }
    }

    }

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        // InputMismatchException -> UnknownError
        if (numChars == -1)
            throw new UnknownError();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new UnknownError();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        } else if (c == '+') {
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(outputStream);
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}

class LatticePoint implements Comparable<LatticePoint> {
    int x;
    int y;

    public LatticePoint(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public String toString() {
        return x + " " + y;
    }

    public int compareTo(LatticePoint that) {
        if (x != that.getX()) {
            return x - that.getX();
        }
        return y - that.getY();
    }

    public double dist(LatticePoint that) {
        return Math.sqrt((double) (x - that.getX()) * (x - that.getX()) + (double) (y - that.getY()) * (y - that.getY()));
    }
}

class MCMF2Double {
    double[][] cost;
    int[][] cap;
    int total_flow;
    double min_cost;
    int n;
    static final double INF = 1e100;

    public MCMF2Double(int n) {
        this.n = n;
        cost = new double[n][n];
        cap = new int[n][n];
    }

    public void add(int u, int v, int edge_cap, double edge_cost) {
        cap[u][v] = edge_cap;
        cost[u][v] = edge_cost;
        cost[v][u] = -edge_cost;
    }

    public int getFlow() {
        return this.total_flow;
    }

    public double getMinCost() {
        return this.min_cost;
    }

    public void run(int source, int sink) {
        double[] pi = new double[n];
        total_flow = 0;
        min_cost = 0;
        while (true) {
            double[] dist = new double[n];
            int[] prev = new int[n];
            Arrays.fill(prev, -1);
            Arrays.fill(dist, INF);

            dist[source] = 0;
            boolean[] visited = new boolean[n];
            while (true) {
                int best_ind = -1;
                for (int i = 0; i < n; ++i) {
                    if (dist[i] < INF / 2 && !visited[i]) {
                        if (best_ind < 0 || dist[i] < dist[best_ind]) {
                            best_ind = i;
                        }
                    }
                }
                if (best_ind < 0) break;
                visited[best_ind] = true;

                for (int i = 0; i < n; ++i) {
                    if (!visited[i] && cap[best_ind][i] > 0) {
                        double edge_cost = pi[best_ind] - pi[i] + cost[best_ind][i];
                        if (dist[i] > dist[best_ind] + edge_cost) {
                            dist[i] = dist[best_ind] + edge_cost;
                            prev[i] = best_ind;
                        }
                    }
                }
            }
            if (!visited[sink]) break;
            ++total_flow;
            min_cost += dist[sink] + pi[sink] - pi[source];
            int cur = sink;
            while (cur != source) {
                int p = prev[cur];
                --cap[p][cur];
                ++cap[cur][p];
                cur = p;
            }
            for (int i = 0; i < n; ++i) {
                if (dist[i] < INF / 2) {
                    pi[i] += dist[i];
                }
            }
        }
    }
}