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 <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <complex>
#include <cstdio>
#include <utility>
#include <queue>
using namespace std;
using W = double;
using P = complex<W>;
using L = pair<P,P>;
using Poly = vector<P>;

#define X real()
#define Y imag()

constexpr W EPS = 1e-8;

namespace std{
  bool operator <(const P &a, const P &b) {
    if (a.X != b.X) return a.X < b.X;
    return a.Y < b.Y;
  }
  bool cmp_y(const P &a, const P &b){
    return a.Y != b.Y ? a.Y < b.Y : a.X < b.X;
  }
}

W dot(P a, P b){ return a.X*b.X + a.Y*b.Y; }
W cross(P a, P b){ return a.X*b.Y - a.Y*b.X; }

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

bool is_cross(L a, L b){
  P af = a.first, as = a.second, bf = b.first, bs = b.second;
  return (ccw(af,as,bf)*ccw(af,as,bs) <= 0 and ccw(bf,bs,af)*ccw(bf,bs,as) <= 0);
}

int in_poly(P a, const Poly &p){
  int n = p.size(), c = 0;
  for(int i = 0; i < n; ++i){
    P s = p[i]-a, t = p[(i+1)%n]-a;
    if(!ccw(s,t,P(0,0))) return 1;
    if(s.Y > t.Y + EPS) swap(s,t);
    if((s.Y*t.Y < 0 or (s.Y*t.Y < EPS and t.Y > EPS)) and cross(s,t) < EPS) ++c;
  }
  if(c%2) return 2;
  return 0;
}

Poly convex_hull(Poly v){
  int n = v.size(), k = 0;
  sort(v.begin(),v.end(),cmp_y);
  Poly r(2*n);
  for(int i = 0; i < n; ++i){
    while(k > 1 and cross(r[k-1]-r[k-2],v[i]-r[k-2]) < -EPS) --k;
    r[k++] = v[i];
  }
  for(int i = n-2, t = k; i >= 0; --i){
    while(k > t and cross(r[k-1]-r[k-2],v[i]-r[k-2]) < -EPS) --k;
    r[k++] = v[i];
  }
  r.resize(k-1);
  return r;
}

W length(const Poly &p){
  W ret = 0;
  int n = p.size();
  for(int i = 0; i < n; ++i)
    ret += abs(p[i]-p[(i+1)%n]);
  return ret;
}

bool is_valid(const Poly &p, const vector<P> &q, int idx){
  for(const auto &e : q){
    if(not in_poly(e,p)) return false;
  }
  int n = p.size();
  idx += n-1;
  for(int k = 0; k < 2; ++k){
    int i = (idx+k)%n;
    for(int j = 0; j < n; ++j){
      if(i == j or (i+1)%n == j or (j+1)%n == i) continue;
      L l1(p[i],p[(i+1)%n]), l2(p[j],p[(j+1)%n]);
      if(is_cross(l2,l1)) return false;
    }
  }
  return true;
}

int main(){
  int n, k;
  while(cin >> n >> k, n){
    int const th = 1;
    Poly v;
    for(int i = 0; i < n; ++i){
      W x, y;
      cin >> x >> y;
      v.emplace_back(x,y);
    }
    Poly C = convex_hull(v);
    priority_queue<W> len;
    priority_queue<pair<W,Poly>> Q;
    W l = length(C);
    len.emplace(l);
    Q.emplace(l,C);
    set<Poly> appeared;
    while(Q.size()){
      Poly p = Q.top().second;
      l = Q.top().first;
      Q.pop();
      vector<P> I;
      for(int i = 0; i < n; ++i){
        bool f = true;
        for(auto e : p){
          if(abs(e-v[i]) < EPS){
            f = false;
            break;
          }
        }
        if(f) I.push_back(v[i]);
      }
      int m = p.size(), t = I.size();
      for(int i = 0; i < m; ++i){
        for(int j = 0; j < t; ++j){
          Poly p_ = p;
          p_.insert(p_.begin()+i+1, I[j]);
          if(not is_valid(p_,v,i+1)) continue;
          if(appeared.count(p_)) continue;
          if(len.size() >= k and len.top() < length(p_)) continue;
          Q.emplace(length(p_),p_);
          if(Q.size() > k*th) Q.pop();
          len.emplace(length(p_));
          if(len.size() > k*th) len.pop();
          appeared.insert(p_);
        }
      }
    }
    if(len.size() < k){
      cout << -1 << endl;
      continue;
    }
    // {
    //   W res = len.top();
    //   while (len.size()) {
    //     fprintf(stderr,"+ %.12f\n",len.top());
    //     len.pop();
    //     //if (len.size()) res = len.top();
    //   }
    //   printf("%.12f\n", res);
    // }
    printf("%.16f\n",len.top());
    // vector<W> res;
    // while (len.size()) {
    //   res.push_back(len.top());
    //   len.pop();
    // }
    // sort(res.begin(), res.end());
    // printf("%.12f\n", res[k-1]);
  }
}