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:
// tabun O(KN^4)

   #include <bits/stdc++.h>
using namespace std;
 #define int long long
 #define ll long long
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-10)


class Point{
	public:
	double x,y;
	Point(double x=0,double y=0):x(x),y(y) {}
	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
	Point operator * (double a) {return Point(x*a,y*a);}
	Point operator / (double a) {return Point(x/a,y/a);}
	double absv() {return sqrt(norm());}
	double norm() {return x*x+y*y;}
	bool operator < (const Point &p) const{
		return x != p.x ? x<p.x: y<p.y;
 	}
	bool operator == (const Point &p) const{
		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
	}
};

double d(Point p,Point q){
	return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}

vector<int> convexhall(vector<Point>  ve){
	sort(ve.begin(),ve.end());
	
	vector<int> ue;
	ue.pb(0);
	int n=ve.size();
	
	for(int i=1;i<n;i++){
		while(1){
			int t=ue.size();
			
			if(t==1){
				ue.pb(i);
				break;
			}
			
			if((ve[ue[t-1]].y-ve[ue[t-2]].y)*(ve[i].x-ve[ue[t-2]].x)<(ve[ue[t-1]].x-ve[ue[t-2]].x)*(ve[i].y-ve[ue[t-2]].y)){
				ue.pop_back();
				continue;
			}
			else{
				ue.pb(i);
				break;
			}
			
		}
	}
	vector<int> si;
	si.pb(0);
	
	for(int i=1;i<n;i++){
		while(1){
			int t=si.size();
			
			if(t==1){
				si.pb(i);
				break;
			}
			
			if((ve[si[t-1]].y-ve[si[t-2]].y)*(ve[i].x-ve[si[t-2]].x)>(ve[si[t-1]].x-ve[si[t-2]].x)*(ve[i].y-ve[si[t-2]].y)){
				si.pop_back();
				continue;
			}
			else{
				si.pb(i);
				break;
			}
			
		}
	}
	
	assert(ue[0]==0);
	assert(si[0]==0);
	assert(ue.back()==n-1);
	assert(si.back()==n-1);
	si.pop_back();
	while(si.size()){
		ue.pb(si.back());
		si.pop_back();
	}
	ue.pop_back();
	return ue;
	
}

double cr(Point x,Point y){
	return x.x*y.y-x.y*y.x;
}

bool kousa(Point xs,Point xt,Point ys,Point yt){
	
	double v1=cr(xt-xs,ys-xs)*cr(yt-xs,xt-xs);
	double v2=cr(yt-ys,xs-ys)*cr(xt-ys,yt-ys);
	
	return (v1>0 && v2>0) ;
}

vector<Point> points;

double nagasa(vector<int> ve){
	int n=ve.size();
	double ans=d(points[ve[0]],points[ve[n-1]]);
	for(int i=0;i<n-1;i++)ans+=d(points[ve[i]],points[ve[i+1]]);
	return ans;
}


bool ok(vector<int> ve,int zen){
	int n=ve.size();
	
	for(int i=0;i<n;i++)for(int j=i+2;j<n;j++){
		//[i,i+1] [j,j+1]
		if(i==0 && j==n-1) continue;
		
		if(kousa(points[ve[i]],points[ve[i+1]],points[ve[j]],points[ve[(j+1)%n]]))return 0;
	}
	
	bool used[30]={};
	for(auto v:ve)used[v]=1;
	for(int v=0;v<zen;v++)if(!used[v]){
		Point X=points[v];
		int cnt=0;
		for(int i=0;i<n;i++){
			Point p=points[ve[i]];
			Point q=points[ve[(i+1)%n]];
			
			if(p.y>q.y)swap(p,q);
			if(p.y>X.y || X.y>q.y)continue;
			if(cr(X-p,q-p)>0)cnt++;
			
		}
		if(cnt%2==0) return 0;
		
	}
	
	
	return 1;
}

double solve(){
	int n,k;
	cin>>n>>k;
	if(n==0) exit(0);
	points.clear();
	for(int i=0;i<n;i++){
		double x,y;
		cin>>x>>y;
		Point p;
		p.x=x*cos(1)+y*sin(1);
		p.y=-x*sin(1)+y*cos(1);
		
		points.pb(p);
	}
	sort(points.begin(),points.end());
	vector<int> CH =convexhall(points);
	
	priority_queue<pair<double,vector<int>>,vector<pair<double,vector<int>>>,greater<pair<double,vector<int>>>> pq;   
	
	pq.push(mp(nagasa(CH),CH));
	set<vector<int>> se;
	int cnt=0;
	while(pq.size()){
		auto Z=pq.top();
		pq.pop();
		
		if(se.count(Z.second))continue;
		
		cnt++;
		
		if(cnt==k){
			return Z.first;
		}
		se.insert(Z.second);
		bool use[30]={};
		for(auto v:Z.second)use[v]=1;
		for(int v=0;v<n;v++)if(!use[v]){
			// vを追加
			int m=Z.second.size();
			for(int i=0;i<m;i++){
				vector<int> NEW;
				for(int j=0;j<m;j++){
					NEW.pb(Z.second[j]);
					if(j==i)NEW.pb(v);
				}
				
				if(ok(NEW,n)){
					
					pq.push(mp(nagasa(NEW),NEW));
				}
				
			}
			
		}
		
	}
	return -1;
}


 signed main(){
 	
 
    	//       cin.tie(0);
   		//	ios::sync_with_stdio(false);
 	while(1){
 		double ans=solve();
 		if(ans<0)printf("-1\n");
 		else printf("%.14lf\n",ans);
 	}
 	
 	return 0;
 
  }