#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i=a; i<(b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define fo(i, n) rep(i, 0, n)
#define F first
#define S second
#define MP make_pair
#define PB push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;

const int NMAX = 20000;
int orig_n, s;

template<class T>
struct Point {
    typedef Point P;
    T x, y;
    explicit Point(T x=0, T y=0): x(x), y(y) {}
    template<class TT> Point(Point<TT> pp): x(pp.x), y(pp.y) {}
    bool operator==(P p) const { return x == p.x && y == p.y; }
    P operator+(P p) const { return P(x+p.x, y+p.y); }
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator*(T c) const { return P(x*c, y*c); }
    P operator/(T c) const { return P(x/c, y/c); }
    T cross(P p) const { return x*p.y - y*p.x; }
    T cross(P a, P b) const { return (a-*this).cross(b-*this); }
    ll dist2() const { return x*(ll)x + y*(ll)y; }
    double dist() const { return sqrt((double) dist2()); }
    P unit() const { return *this/dist(); }
};
typedef vector<Point<int>> vp;
typedef Point<int> P;
typedef Point<double> DP;

int up[NMAX];
int upp(int i) {
	if (up[i] == i) return i;
	return up[i] = upp(up[i]);
}

void merge(int a, int b) {
	a = upp(a);
	b = upp(b);
	if (a != b)
		up[a] = b;
}

struct Solution {
	vp points;
	vpii edges;
	double cost() {
		double res = (sz(points)-orig_n)*s;
		for (auto e: edges) {
			res += (points[e.F]-points[e.S]).dist();
		}
		return res;
	}

    void procisti()
    {
	fo(i,NMAX) up[i]=i;

        sort(all(edges), [&](auto const& e1, auto const& e2) {return (points[e1.F]-points[e1.S]).dist2() < (points[e2.F]-points[e2.S]).dist2();});

	vpii out = {};
	for(auto e : edges)
	{
		if(upp(e.F) != upp(e.S))
		{
			out.PB(e);
			merge(e.F, e.S);
		}
	}
	edges = out;
    }
};

P sample(const vp& points) {
	if (sz(points) < 10)
		return points[rand()%sz(points)];
	int minxd = INT_MAX;
	int maxxd = INT_MIN;
	int minyd = INT_MAX;
	int maxyd = INT_MIN;
	for (auto p: points) {
		minxd = min(minxd, p.x);
		maxxd = max(maxxd, p.x);
		minyd = min(minyd, p.y);
		maxyd = max(maxyd, p.y);
	}
	int rx = (maxxd - minxd)/10+1;
	int ry = (maxyd - minyd)/10+1;
	vector<vp> buckets(115);
	for(auto p: points) {
		buckets[10LL*((p.x - minxd) / rx) + (p.y - minyd) / ry].PB(p);
	}
	vi b;
	for (int i=0; i<sz(buckets); i++) {
		if (sz(buckets[i]))
			b.PB(i);
	}
	return sample(buckets[b[rand()%sz(b)]]);
}

DP lineInter(DP s1, DP e1, DP s2, DP e2) {
    auto d = (e1 - s1).cross(e2 - s2);
    if (d == 0)
        return DP(0, 0);
    auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
    return (s1 * p + e1 * q) / d;
}

P goodPoint(DP a, DP b, DP c) {
    P ap = a + (b - a).unit() + (c - a.unit());
    P bp = a + (c - b).unit() + (a - b.unit());
    return lineInter(a, ap, b, bp);
}

vpii calc_st(vp &points)
{
	int n = sz(points);
	ll dists[NMAX];
	ll dists_source[NMAX];
	bool used[NMAX];

	fo(i,n) used[i]=0;
	used[0] = 1;
	fo(i, n) dists[i] = (points[0] - points[i]).dist2();
	fo(i,n) dists_source[i]=0;
	
	vpii out;

	fo(_,n-1)
	{

		int minj=-1;
		fo(j,n) if(!used[j])
		{
			if(minj==-1 || dists[j] < dists[minj])
				minj = j;
		}
		used[minj] = 1;
		out.push_back(MP(minj, dists_source[minj]));
		fo(k, n)
		{
			if((points[minj] - points[k]).dist2() < dists[k])
			{
				dists[k] = (points[minj] - points[k]).dist2();
				dists_source[k] = minj;
			}
		}
	}
	return out;
}

signed main() {
    // cin.excepo"tions(cin.failbit);
    cin >> orig_n >> s;
    int n = orig_n;
    vp points(n);
    fo(i,n) cin >> points[i].x >> points[i].y;

    Solution solution;
    solution.points = points;
    solution.edges = calc_st(points);

    fo(iiiii, 14500) {
        P a = sample(solution.points);
        P b = sample(solution.points);
        P c = sample(solution.points);

        if (a == b) continue;
        if (a == c) continue;
        if (b == c) continue;

        P p = goodPoint(a, b, c);
        Solution ns = solution;
        ns.points.PB(p);
	fo(i, sz(ns.points)-1) {
		ns.edges.PB({i, sz(ns.points)-1});
	}
        ns.procisti();
        if (ns.cost() < solution.cost())
            solution = ns;
    }

    printf("%d %d\n", sz(solution.points) - orig_n, sz(solution.edges));
    rep(i, orig_n, sz(solution.points)) {
	    printf("%d %d\n", solution.points[i].x, solution.points[i].y);
    }
    for(auto x: solution.edges)
    {
	    printf("%d %d\n", x.F+1, x.S+1);
    }
    // printf("%lf", solution.cost());
}