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:
/* Codeforces Template */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
	
	static long initTime;
	static final Random rnd = new Random(7777L);
	static boolean writeLog = false;
	
	public static void main(String[] args) throws IOException {
		initTime = System.currentTimeMillis();
		try {
			writeLog = "true".equals(System.getProperty("LOCAL_RUN_7777"));
		} catch (SecurityException e) {}
		new Thread(null, new Runnable() {
			public void run() {
				try {
					try {
						if (new File("input.txt").exists())
							System.setIn(new FileInputStream("input.txt"));
					} catch (SecurityException e) {}
					long prevTime = System.currentTimeMillis();
					new Main().run();
					log("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
					log("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
		in.close();
	}
	
	/*************************************************************** 
	 * Solution
	 **************************************************************/

	final double INF = 1e100;
	
	int n;
	int vNum;
	int S, T;
	int[] xs;
	int[] ys;
	
	Net net;
	
	void solve() throws IOException  {
		
		n = nextInt();
		xs = new int [n];
		ys = new int [n];
		
		for (int i = 0; i < n; i++) {
			xs[i] = nextInt();
			ys[i] = nextInt();
		}
		
		vNum = n + n + 2;
		S = vNum - 2;
		T = vNum - 1;
		
		Net net = new Net(vNum, n + n + n * n);
		
		for (int i = 0; i < n; i++) {
			net.addDirectedEdge(-1, S, i, 2, 0);
			net.addDirectedEdge(-1, n + i, T, 1, 0);
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (ys[i] > ys[j]) {
					net.addDirectedEdge(-1, i, n + j, 1, dist(xs[i], ys[i], xs[j], ys[j]));
				}
			}
		}
		
		MinCostFlowAlgo mcf = new MinCostFlowAlgo(net, S, T);
		
		
		boolean ok = mcf.minCostFlow(n - 1);
		
		if (ok) {
			out.println(mcf.cost);
		} else {
			out.println(-1);
		}
		
	}
	
	double dist(double x1, double y1, double x2, double y2) {
		return sqrt(sqr(x2 - x1) + sqr(y2 - y1));
	}
	
	double sqr(double x) {
		return x * x;
	}
	
	class MinCostFlowAlgo {
		Net net;
		double[] dist;
		boolean[] used;
		double[] phi;
		NetEdge[] prev;
		int tick = 1;
		
		int S, T;
		double cost;
		int flow;
		
		MinCostFlowAlgo(Net net, int S, int T) {
			this.net = net;
			dist = new double [net.vNum];
			used = new boolean [net.vNum];
			phi = new double [net.vNum];
			prev = new NetEdge [net.vNum];
			
			this.S = S;
			this.T = T;
		}
		
		void calcPotencials() {
			fill(phi, INF);
			phi[S] = 0;
			for (int it = 0; it < net.vNum; it++)
				for (int v = 0; v < net.vNum; v++)
					if (phi[v] != INF)
						for (int i = net.head[v]; i != 0; i = net.next[i]) {
							NetEdge e = net.edge[i];
							if (e.capacity > 0 && phi[e.to] > phi[v] + e.cost)
								phi[e.to] = phi[v] + e.cost;
						}
		}
		
		boolean minCostFlow(int K) {
			cost = flow = 0;
			while (flow < K)
				if (dijkstra() != INF)
					updateFlow(K);
				else
					return false;
			return true;
		}

		double dijkstra() {
			fill(dist, INF);
			fill(used, false);
			dist[S] = 0;
			
			while (true) {
				int v = -1;
				for (int i = 0; i < net.vNum; i++)
					if (!used[i] && dist[i] != INF && (v == -1 || dist[v] > dist[i]))
						v = i;
				if (v == -1)
					break;
				used[v] = true;
				for (int i = net.head[v]; i != 0; i = net.next[i]) {
					NetEdge e = net.edge[i];
					if (!used[e.to] && e.restCapacity() > 0)
						if (dist[e.to] > dist[v] + e.cost + phi[v] - phi[e.to]) {
							dist[e.to] = dist[v] + e.cost + phi[v] - phi[e.to];
							prev[e.to] = e;
						}
				}
			}
			
			return dist[T];
		}
		
		void updateFlow(int rest) {
			int addFlow = rest - flow;
			for (int v = T; v != S; v = prev[v].from)
				addFlow = min(addFlow, prev[v].restCapacity());
			for (int v = T; v != S; v = prev[v].from)
				cost += prev[v].inc(addFlow);
			flow += addFlow;
			for (int v = 0; v < net.vNum; v++)
				phi[v] += dist[v] != INF ? dist[v] : dist[T];
		}
	}
	
	class NetEdge {
		int id;
		int from;
		int to;
		int capacity;
		int flow;
		double cost;
		NetEdge back;
		
		NetEdge(int id, int from, int to, int capacity, double cost) {
			this.id = id;
			this.from = from;
			this.to = to;
			this.capacity = capacity;
			this.cost = cost;
		}
		
		int restCapacity() {
			return capacity - flow;
		}
		
		void connect(NetEdge back) {
			this.back = back;
		}
		
		double inc(int addFlow) {
			flow += addFlow;
			back.flow -= addFlow;
			return cost * addFlow;
		}
	}
	
	class Net {
		int vNum;
		int[] head;
		int[] next;
		NetEdge[] edge;
		int cnt = 1;
		
		Net(int vNum, int eNum) {
			this.vNum = vNum;
			head = new int [vNum];
			next = new int [2 * eNum + 1];
			edge = new NetEdge [2 * eNum + 1];
		}
		
		void add(int v, NetEdge e) {
			next[cnt] = head[v];
			edge[cnt] = e;
			head[v] = cnt++;
		}
		
		void addDirectedEdge(int id, int from, int to, int capacity, double cost) {
			NetEdge forward = new NetEdge(id, from, to, capacity, cost);
			NetEdge back = new NetEdge(id, to, from, 0, -cost);
			forward.connect(back);
			back.connect(forward);
			this.add(from, forward);
			this.add(to, back);
		}
		
		void addUndirectedEdge(int id, int from, int to, int capacity, double cost) {
			this.addDirectedEdge(id, from, to, capacity, cost);
			this.addDirectedEdge(id, to, from, capacity, cost);
		}
	}
	
	/*************************************************************** 
	 * Input 
	 **************************************************************/
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextInt();
		return ret;
	}
	
	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextLong();
		return ret;
	}
	
	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextDouble();
		return ret;
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
	
	/*************************************************************** 
	 * Output 
	 **************************************************************/
	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}
	
	void printArray(int[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(long[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}
	
	void printArray(Object[] array) {
		if (array == null || array.length == 0)
			return;
		boolean blank = false;
		for (Object x : array) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty())
			return;
		boolean blank = false;
		for (Object x : collection) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	/*************************************************************** 
	 * Utility
	 **************************************************************/
	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
	
	static void checkMemory() {
		System.err.println(memoryStatus());
	}
	
	static long prevTimeStamp = Long.MIN_VALUE;
	
	static void updateTimer() {
		prevTimeStamp = System.currentTimeMillis();
	}
	
	static long elapsedTime() {
		return (System.currentTimeMillis() - prevTimeStamp);
	}
	
	static void checkTimer() {
		System.err.println(elapsedTime() + " ms");
	}
	
	static void chk(boolean f) {
		if (!f) throw new RuntimeException("Assert failed");
	}
	
	static void chk(boolean f, String format, Object ... args) {
		if (!f) throw new RuntimeException(String.format(format, args));
	}
	
	static void log(String format, Object ... args) {
		if (writeLog) System.err.println(String.format(Locale.US, format, args));
	}
}