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>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
 
using namespace std;
 
typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;
 
const int MAX_N = 100005;
const double s3 = sqrt(3.0);
 
inline double rpos(P& p, int y){
    return (s3*p.fi+p.se-y)*s3/3.0;
}
 
inline double lpos(P& p, int y){
    return (s3*p.fi-p.se+y)*s3/3.0;
}
 
#define getchar getchar_unlocked
 
inline int in() {
    int n = 0; short c; bool flag = false;
    if((c = getchar()) < '0') flag = true; else n = c - '0';
    while ((c = getchar()) >= '0') n = n * 10 + c - '0';
    return flag ? -n : n;
}
 
int main()
{
    while(1){
        int n = in();
        if(n == 0) break;
        int K = in();
        map<int,int> mp;
        vp l(n),r(n);
        rep(i,n){
            int a = in(), b = in();
            mp[b]++;
            l[i] = P(a,b), r[i] = P(a,b);
        }
        sort(all(l),[&](P& a, P& b){
            return a.se-s3*a.fi < b.se-s3*b.fi;
        });
        sort(all(r),[&](P& a, P& b){
            return a.se+s3*a.fi < b.se+s3*b.fi;
        });
        double ans = 1e100;
        int cnt = 0;
        each(it,mp){
            if(cnt > K) break;
            int lid, rid;
            int made = 0;
            for(rid = 0; rid < n; rid++){
                if(r[rid].se + EPS >= it.fi){
                    if(++made == n-K) break;
                }
            }
            for(lid = n-1; lid >= 0; lid--){
                if(l[lid].se + EPS >= it.fi && l[lid].se <= -s3*l[lid].fi + r[rid].se + s3*r[rid].fi + EPS) break;
            }
            cmn(ans, rpos(r[rid],it.fi)-lpos(l[lid],it.fi));
            rep(i,K-cnt){
                bool ok = false;
                rid++;
                for(; rid < n; rid++){
                    if(r[rid].se + EPS >= it.fi && r[rid].se <= s3*r[rid].fi + l[lid].se - s3*l[lid].fi + EPS){
                        ok = true;
                        break;
                    }
                }
                if(!ok) break;
                ok = false;
                lid--;
                for(; lid >= 1; lid--){
                    if(l[lid].se + EPS >= it.fi && l[lid].se <= -s3*l[lid].fi + r[rid].se + s3*r[rid].fi + EPS){
                        ok = true;
                        break;
                    }
                }
                if(!ok) break;
                cmn(ans, rpos(r[rid],it.fi)-lpos(l[lid],it.fi));
            }
            cnt += it.se;
        }
        printf("%.12lf\n", 3.0*ans);
    }
    return 0;
}