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 N 10001
using namespace std;

typedef double dbl;
const dbl pi = acos(-1), eps = 1e-6;
struct vec { dbl x, y; };
inline bool operator<(vec v1, vec v2) { return v1.y == v2.y ? v1.x < v2.x : v1.y < v2.y; }
inline vec operator+(vec v1, vec v2) { return { v1.x + v2.x, v1.y + v2.y }; }
inline vec operator-(vec v1, vec v2) { return { v1.x - v2.x, v1.y - v2.y }; }
inline dbl operator*(vec v1, vec v2) { return v1.x * v2.x + v1.y * v2.y; }
inline dbl operator^(vec v1, vec v2) { return v1.x * v2.y - v1.y * v2.x; }
inline vec operator*(vec v, dbl k) { return { v.x * k, v.y * k }; }
inline vec operator/(vec v, dbl k) { return { v.x / k, v.y / k }; }
inline dbl crx(vec p0, vec p1, vec p2) { return (p1 - p0) ^ (p2 - p0); }
struct line { vec p, v; };
inline vec litsc(line l1, line l2) { return l2.p+l2.v*((l1.v^(l2.p-l1.p))/(l2.v^l1.v)); }

vec ps[N];
dbl w[N];
typedef pair<double, int> pdi;
pdi ep[N << 1]; int vis[N];
pdi p1[N], p2[N], q1[N], q2[N];
bool operator<(pdi p1, pdi p2) { return p1.first < p2.first - eps; }

int main(void) {
//    freopen("in", "r", stdin);
//    freopen("out", "w", stdout);
    #ifndef ONLINE_JUDGE
    #endif // ONLINE_JUDGE
    int n, k;
    const dbl s3 = sqrt(3);
    const vec vl = { 1. / 2, s3 / 2 };
    const vec vr = { -1. / 2, s3 / 2 };
    while (scanf("%d", &n), n) {
        scanf("%d", &k);
        for (int i = 1; i <= n; ++i)
            scanf("%lf%lf", &ps[i].x, &ps[i].y);
        sort(ps + 1, ps + n + 1);
        for (int i = 1; i <= n; ++i) {
            p1[i] = { ps[i] * vec{ sqrt(3) / 2,  -1. / 2 }, i };
            p2[i] = { ps[i] * vec{ sqrt(3) / 2,  1. / 2 }, i };
        }
        sort(p1 + 1, p1 + n + 1);
        sort(p2 + 1, p2 + n + 1);
//        for (int i = 1; i <= n; ++i)
//            cout << p1[i].second << '\t' << p2[i].second << endl;
        for (int i = 1; i <= n; ++i) w[i] = ps[i].y;
        int m = unique(w + 1, w + n + 1) - w - 1;
        //cout << m << ' ' << n << endl;
        dbl ans = DBL_MAX;
        int c = 2 * n;
        for (int i = 1; i <= m; ++i) {
            int c1 = remove_if(p1 + 1, p1 + c / 2 + 1, [&](pdi p) { return ps[p.second].y < w[i]; }) - p1 - 1;
            int c2 = remove_if(p2 + 1, p2 + c / 2 + 1, [&](pdi p) { return ps[p.second].y < w[i]; }) - p2 - 1;
            assert(c1 == c2);
            for (int j = 1; j <= c1; ++j) {
                int j1 = p1[j].second, j2 = p2[j].second;
                q1[j] = { (w[i] - ps[j1].y) / s3 + ps[j1].x, -j1 };
                q2[j] = { -(w[i] - ps[j2].y) / s3 + ps[j2].x, j2 };
                vis[j1] = vis[j2] = 0;
//                cout << j1 << ' ' << j2 << endl;
//                cout << q1[j].first << '\t' << q2[j].first << endl;
            }
            //assert(is_sorted(q1 + 1, q1 + c1 + 1));
            //assert(is_sorted(q2 + 1, q2 + c2 + 1));
            if (c / 2 < n - k) {
                //cout << "! " << m - i << ' ' << m << ' ';
                break;
            }
            c = c1 + c2;
            merge(q1 + 1, q1 + c1 + 1, q2 + 1, q2 + c2 + 1, ep + 1);
            //sort(ep + 1, ep + c + 1);
            //assert(is_sorted(ep + 1, ep + c + 1));
//            for (int j = 1; j <= c; ++j)
//                cout << ep[j].first << ' ' << ep[j].second << endl;
//            cout << endl;
            int cnt = 0;
            for (int l = 1, r = 0; l <= c; ++l) {
                vec p = { ep[l].first, w[i] };
                while (cnt < n - k && r < c) {
                    ++r;
                    int id = ep[r].second;
                    if (id > 0 && !vis[id] && (vl ^ (ps[id] - p)) <= eps) {
                        vis[id] = 1;
                        cnt++;
                    }
                }
                if (cnt >= n - k)
                    ans = min(ans, (dbl)(ep[r].first - ep[l].first));
                else break;
                int id = ep[l].second;
                if (id < 0) {
                    if (vis[-id] == 1) {
                        vis[-id] = 0;
                        cnt--;
                    }
                    else {
                        vis[-id] = -1;
                    }
                }
            }
        }
        printf("%.7f\n", 3 * ans);
    }

    return 0;
}