Problem: K is a polygonal Kay

"Do I have to be No. 1? Is it not No. K?"

This is Mr. Kay's inscription. Recently, Mr. Kay seems to be exclusively interested in polygons, seeing N points placed on a vast two-dimensional plane spreading in front of him, and thinking about how to form polygons from them. There is. Apparently, Kay decided to select some of these N points and connect them in any order to form a polygon with the selected points as vertices. However, polygons must meet the following conditions.

* It is a simple polygon. That is, it has three or more vertices, and any two non-contiguous sides do not have an intersection.
* Includes all N points, including non-selected points, inside or on the circumference.



According to his belief, Mr. Kay is hungry for a polygon whose perimeter, that is, the sum of the lengths of all sides, is the Kth shortest among such polygons.

Your job is to help Mr. Kay by writing a program that finds the Kth polygon among the polygons that satisfy the conditions and arranges them in ascending order of perimeter, and outputs the perimeter. However, there may be no more than K such polygons. In such a case, it is necessary to output -1 with apologetic feelings while considering Mr. Kay's remorse.

Input

The input consists of multiple datasets. Each dataset is represented in the following format.

> N K x1 y1 ... xN yN

The first row of the dataset is given the number N of points on the two-dimensional plane and the rank K of the perimeter to be found. Both N and K are integers, and 3 ≤ N ≤ 25, 1 ≤ K ≤ 10 holds. The following N lines give the coordinates of each point on the two-dimensional plane. On the i-th line of the N-line, the x-coordinate xi and the y-coordinate yi of the i-th point are both given as integers, and -100 ≤ xi, yi ≤ 100 holds for all 1 ≤ i ≤ N. No matter which of the three different points you choose, you can assume that there is no straight line that passes through all three points. In addition, it can be assumed that the polygon that satisfies the condition described in the problem statement, which is the Kth polygon when arranged in ascending order of perimeter, is uniquely determined if it exists.

The end of the input is represented by a line consisting of only two zeros. The total number of all datasets does not exceed 50.

Output

When creating a simple polygon by selecting some points from a given set of points, output the perimeter of the K-th shortest perimeter of the configurable simple polygons on one line. If such a polygon does not exist, output -1. The result should not contain more than 10-4 errors.

Sample Input


5 2
1 1
14
twenty two
3 1
3 5
3 1
0 2
Ten
-Ten
3 2
0 2
Ten
-Ten
9 10
8 1
9 19
2 10
1 1
4 17
7 13
3 4
6 13
9 21
0 0


Output for the Sample Input


11.812559200041266
6.472135954999580
-1
52.202878812480016






Example

Input

5 2
1 1
1 4
2 2
3 1
3 5
3 1
0 2
1 0
-1 0
3 2
0 2
1 0
-1 0
9 10
8 1
9 19
2 10
1 1
4 17
7 13
3 4
6 13
9 21
0 0


Output

11.812559200041266
6.472135954999580
-1
52.202878812480016

Solution (in CPP):

Solution:
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <set>
#include <map>
using namespace std;

#define ALL(v) (v).begin(),(v).end()

typedef double D;
typedef complex<D> P;
typedef const P &rP;

const D EPS = 1e-9;

namespace std{
	bool operator< (const P &p, const P &q){
		if(p.real() != q.real()){ return p.real() < q.real(); }
		return p.imag() < q.imag();
	}
}

void normalize(vector<int> &v){
	rotate(v.begin(), min_element(ALL(v)), v.end());
}

D dot(rP va, rP vb){
	return real(va) * real(vb) + imag(va) * imag(vb);
}

D cross(rP va, rP vb){
	return real(va) * imag(vb) - imag(va) * real(vb);
}

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

bool intersectSS(P pa1, P pa2, P pb1, P pb2){
	P da12 = pa2 - pa1;
	P db21 = pb1 - pb2;
	P dab1 = pb1 - pa1;

	D d = cross(da12, db21);

	if(abs(d) > EPS){
		D t = cross(dab1, db21) / d;
		D s = cross(da12, dab1) / d;
		
		if( (-EPS < t && t < 1.0 + EPS) && (-EPS < s && s < 1.0 + EPS) ){
			return true;
		}
	}
	return false;
}

bool containstript(rP a, rP b, rP c, rP pt){
	int x = ccw(a, b, pt);
	int y = ccw(b, c, pt);
	int z = ccw(c, a, pt);
	if(x == 1 && y == 1 && z == 1){ return true; }
	if(x == -1 && y == -1 && z == -1){ return true; }
	return false;
}

vector<P> convex_hull(vector<P> ps) {
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());

	vector<P> ch(2*n);
	for (int i = 0; i < n; ch[k++] = ps[i++]){ // lower-hull
		while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
	}
	for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]){ // upper-hull
		while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
	}
	ch.resize(k-1);
	return ch;
}

struct solver{
	struct polygon{
		D len;
		vector<int> idxs;

		polygon(D l, const vector<int> &i) : len(l), idxs(i) {}

		bool operator< (const polygon &p) const{
			return len < p.len;
		}
	};

	rP getpt(const vector<int> &v, size_t i){
		return points[i == v.size() ? v[0] : v[i]];
	}

	size_t k;
	vector<P> points;
	map<P,int> toidx;
	vector<polygon> pols;
	set<vector<int>> seen;
	
	polygon makeplg(vector<int> idxs){
		normalize(idxs);
		int sz = idxs.size();
		D len = 0;
		for(int i = 0; i < sz; ++i){
			len += abs(getpt(idxs, i) - getpt(idxs, i + 1));
		}
		return polygon(len, idxs);
	}

	void add(const vector<int> &w){
		set<int> st;
		for(int x : w){
			if(!st.insert(x).second){ return; }
		}
		polygon pl = makeplg(w);
		if(seen.insert(pl.idxs).second){
			pols.insert(upper_bound(ALL(pols), pl), pl);
			while(pols.size() > k){ pols.pop_back(); }
		}
	}
	
	void validateadd(const vector<int> &v, int pos, int pi){
		int sz = v.size();
		for(int i = 0; i < sz; ++i){
			if(i + 1 == pos){ continue; }
			if(!(pos == 1 && i == sz - 1) && i + 2 != pos){
				if(intersectSS(getpt(v, i), getpt(v, i + 1), getpt(v, pos - 1), points[pi])){
					return;
				}
			}
			if(pos != i && !(pos == sz && i == 0)){
				if(intersectSS(getpt(v, i), getpt(v, i + 1), points[pi], getpt(v, pos))){
					return;
				}
			}
		}
		for(rP c : points){
			if(containstript(getpt(v, pos - 1), points[pi], getpt(v, pos), c)){
				return;
			}
		}
		vector<int> w = v;
		w.insert(w.begin() + pos, pi);
		add(w);
	}

	D solve(int n, int k_){
		k = k_;
		for(int i = 0; i < n; ++i){
			D x, y;
			cin >> x >> y;
			P p(x, y);
			points.push_back(p);
			toidx[p] = i;
		}

		vector<P> conv0 = convex_hull(points);
		vector<int> v0;
		for(rP p : conv0){
			v0.push_back(toidx[p]);
		}
		add(v0);

		for(size_t i = 0; i < pols.size(); ++i){
			polygon cur = pols[i];
			int sz = cur.idxs.size();
			for(int pos = 1; pos <= sz; ++pos)
			for(int pi = 0; pi < n; ++pi){
				validateadd(cur.idxs, pos, pi);
			}
		}

		if(pols.size() >= k){
			return pols[k - 1].len;
		}
		return -1;
	}
};

int main(){
	cout << fixed << setprecision(9);

	int n, k;
	while(cin >> n >> k && n){
		D ans = solver().solve(n, k);
		cout << ans << endl;
	}
}