Problem: Equilateral Triangular Fence

Ms. Misumi owns an orchard along a straight road. Recently, wild boars have been witnessed strolling around the orchard aiming at pears, and she plans to construct a fence around many of the pear trees.

The orchard contains n pear trees, whose locations are given by the two-dimensional Euclidean coordinates (x1, y1),..., (xn, yn). For simplicity, we neglect the thickness of pear trees. Ms. Misumi's aesthetic tells that the fence has to form a equilateral triangle with one of its edges parallel to the road. Its opposite apex, of course, should be apart from the road. The coordinate system for the positions of the pear trees is chosen so that the road is expressed as y = 0, and the pear trees are located at y ≥ 1.

Due to budget constraints, Ms. Misumi decided to allow at most k trees to be left outside of the fence. You are to find the shortest possible perimeter of the fence on this condition.

The following figure shows the first dataset of the Sample Input. There are four pear trees at (−1,2), (0,1), (1,2), and (2,1). By excluding (−1,2) from the fence, we obtain the equilateral triangle with perimeter 6.

<image>

Input

The input consists of multiple datasets, each in the following format.

> n
>  k
>  x1 y1
>  ...
>  xn yn
>

Each of the datasets consists of n+2 lines. n in the first line is the integer representing the number of pear trees; it satisfies 3 ≤ n ≤ 10 000. k in the second line is the integer representing the number of pear trees that may be left outside of the fence; it satisfies 1 ≤ k ≤ min(n−2, 5 000). The following n lines have two integers each representing the x- and y- coordinates, in this order, of the locations of pear trees; it satisfies −10 000 ≤ xi ≤ 10 000, 1 ≤ yi ≤ 10 000. No two pear trees are at the same location, i.e., (xi, yi)=(xj, yj) only if i=j.

The end of the input is indicated by a line containing a zero. The number of datasets is at most 100.

Output

For each dataset, output a single number that represents the shortest possible perimeter of the fence. The output must not contain an error greater than 10−6.

Sample Input


4
1
0 1
1 2
-1 2
2 1
4
1
1 1
2 2
1 3
1 4
4
1
1 1
2 2
3 1
4 1
4
1
1 2
2 1
3 2
4 2
5
2
0 1
0 2
0 3
0 4
0 5
6
3
0 2
2 2
1 1
0 3
2 3
1 4
0


Output for the Sample Input


6.000000000000
6.928203230276
6.000000000000
7.732050807569
6.928203230276
6.000000000000






Example

Input

4
1
0 1
1 2
-1 2
2 1
4
1
1 1
2 2
1 3
1 4
4
1
1 1
2 2
3 1
4 1
4
1
1 2
2 1
3 2
4 2
5
2
0 1
0 2
0 3
0 4
0 5
6
3
0 2
2 2
1 1
0 3
2 3
1 4
0


Output

6.000000000000
6.928203230276
6.000000000000
7.732050807569
6.928203230276
6.000000000000

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int mod = 1e9 + 7;

#define dump(x) ([&](){auto ___val = (x); cout << #x << " = " << (___val) << endl; })();
// #define dump(x) ;


template<class T>
ostream&operator<<(ostream &os, vector<T>v) {
  os << "{";
  for(size_t i = 0; i < v.size(); i++) os << v[i] << ", ";
  os << "}";
  return os;
}

template<class T, class U>
ostream&operator<<(ostream &os, pair<T, U>v) {
  os << "(" << v.first << " , " << v.second << ")";
  return os;
}

template<class T, class U>
ostream&operator<<(ostream &os, map<T, U>v) {
  os << "(map: \n";
  for(auto e : v) os << e << ", \n";
  os << ")";
  return os;
}

template<class T>
ostream&operator<<(ostream &os, set<T>v) {
  os << "(set: \n";
  for(auto e : v) os << e << ", \n";
  os << ")";
  return os;
}

using Vec = vector<int>;
using Mat = vector<Vec>;

ll modpow(ll x, ll k, ll mod) {
  x %= mod;
  ll r = 1;
  assert(k >= 0);
  while(k) {
    if(k & 1) r = r * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return r;
}

ll toint(string s) {
  ll res = 0;
  int n = s.size();
  for(int i = 0; i < n; i++) res |= (ll(s[n - 1 - i] - '0')) << i;
  return res;
}

string tostr(ll x, int n) {
  string res = "";
  for(int i = 0; i < n; i++) {
    res += '0' + ((x >> i) & 1);
  }
  reverse(begin(res), end(res));
  return res;
}

bool mul_OF(ll a, ll b) {
  // a * b > 4e18
  // a > floor(4e18 / b)
  return a > ll(1e18) / b;
}


// O(k^2) が間に合うのか…

int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  const double r3 = sqrt(3);

  while(1) {
    int n, k;
    cin >> n;
    if(!n) break;
    cin >> k;
    vector<double> x(n), y(n);
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    vector<double> kL(n), kR(n);
    for(int i = 0; i < n; i++) kL[i] = -(y[i] - r3 * x[i]), kR[i] = y[i] + r3 * x[i];
    vector<int> yord(n);
    iota(begin(yord), end(yord), 0);
    sort(begin(yord), end(yord), [&](int i, int j) {
        return y[i] < y[j];
        });

    using P = pair<double, int>;
    set<P> kLord, kRord;

    for(int i = 0; i < n; i++) kLord.emplace(kL[i], i);
    for(int i = 0; i < n; i++) kRord.emplace(kR[i], i);

    vector<int> kL_rank(n);
    vector<int> kR_rank(n);

    {
      auto ite = kLord.begin();
      for(int i = 0; i < n; i++, ite++) kL_rank[ite->second] = i;
    }
    {
      auto ite = kRord.begin();
      for(int i = 0; i < n; i++, ite++) kR_rank[ite->second] = i;
    }

    // yの昇順に, 捨てていって,
    // 右側を最大捨てて,
    // 右を左に動かしていく

    // dump(kLord);
    // dump(kRord);

    double ans = 1e18;

    for(int i = 0; i <= k; i++) {
      assert(n - i == kLord.size());
      assert(n - i == kRord.size());

      int drop = 0;
      int yid = yord[i];
      int ab = k - i;
      double ycord = y[yid];
      // 捨てる
      auto iteR = kRord.end();
      auto iteL = kLord.begin();
      for(int rem = 0; rem < ab && iteR != kRord.begin(); rem++, iteR--) ;
      assert(iteR != kRord.begin());
      while(1) {
        int lid = iteL->second;
        int rid = prev(iteR)->second;
        // dump(x[lid]); dump(y[lid]);
        while(kR_rank[lid] > kR_rank[rid] || drop) {
          // dump(drop);
          if(kR_rank[lid] > kR_rank[rid]); else drop--;
          iteL++;
          assert(iteL != kLord.end());
          lid = iteL->second;

        }
        double L = 
          - 1.0 / r3 * (ycord - kR[rid])
          - 1.0 / r3 * (ycord + kL[lid]);
        ans = min(ans, L);

        // dump(ycord);
        // dump(x[rid]); dump(y[rid]);
        // dump(x[lid]); dump(y[lid]);
        // dump(L);
        // dump("");

        if(iteR == kRord.end()) break;
        iteR++;
        rid = prev(iteR)->second;
        if(kL_rank[lid] < kL_rank[rid]) drop++;
      }


      // y 座標的に捨てる
      kLord.erase(make_pair(kL[yid], yid));
      kRord.erase(make_pair(kR[yid], yid));
    }

    cout << fixed << setprecision(20) << ans * 3 << "\n";
  }
}