#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()
template<typename T> bool chmax(T &x, const T &y) {return (x<y)?(x=y,true):false;};
template<typename T> bool chmin(T &x, const T &y) {return (x>y)?(x=y,true):false;};
constexpr ll MOD=998244353;
constexpr ll INF=2e18;

const bool DEBUG=0;

struct Point{
    int x, y;
};

inline int pdist(const Point& p1, const Point& p2){
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

const double TL=0.9;
const double T0=800;
const double T1=10;
double start, T;

int alp=5;
int N, M;
vector<Point> P(100);

Point cog(const set<int>& s){
    int sz=s.size();
    int xsum=0, ysum=0;
    for(auto i:s){
        xsum+=P[i].x;
        ysum+=P[i].y;
    }
    return {xsum/sz,ysum/sz};
}

void input(){
    cin >> N >> M;
    REP(i,N) cin >> P[i].x >> P[i].y;
}

void input_debug(int fnum){
    string name="";
    if(fnum<1000) name+='0';
    if(fnum<100) name+='0';
    if(fnum<10) name+='0';
    name+=to_string(fnum);
    name+=".txt";
    ifstream ifs(("/mnt/c/CP/work/input/"+name).c_str(),ios::in);
    if(!ifs)
        cout << "error" << endl;
    cout << name << " ";
    ifs >> N >> M;
    REP(i,N) ifs >> P[i].x >> P[i].y;
}

ll solve(){
    vector<vector<int>> dist(N,vector<int>(N));
    REP(i,N)REP(j,N) dist[i][j]=pdist(P[i],P[j]);
    vector<int> ord(N);
    iota(ALL(ord),0);
    vector<set<int>> sss(M);
    REP(i,M) sss[i]={ord[i],ord[(i+1)%N]};
    vector<Point> ssp(M);
    REP(i,M) ssp[i]=cog(sss[i]);
    ll cost=0, mincost=INF;
    REP(i,N) cost+=alp*alp*dist[ord[i]][ord[(i+1)%N]];
    vector<Point> ansssp;
    vector<vector<pair<int,int>>> ans;
    int rcnt=0;
    for(rcnt=0;true;rcnt++){
        int rx, ry, r1, r2;
        rx=rand()%4;
        if(rx!=0){
            r1=rand()%N+1;
            r2=rand()%N+1;
            if(r1>r2) swap(r1,r2);
            reverse(ord.begin()+r1,ord.begin()+r2);
        }
        else{
            ry=rand()%2;
            if(ry==0){
                r1=rand()%M;
                r2=rand()%N;
                if(sss[r1].find(r2)!=sss[r1].end())
                    continue;
                sss[r1].insert(r2);
                ssp[r1]=cog(sss[r1]);
            }
            else{
                r1=rand()%M;
                r2=rand()%N;
                if(sss[r1].size()==2)
                    continue;
                if(sss[r1].find(r2)==sss[r1].end())
                    continue;
                sss[r1].erase(r2);
                ssp[r1]=cog(sss[r1]);
            }
        }
        vector<vector<pair<int,int>>> pans(N);
        ll newcost=0;
        REP(i,N){
            ll mcost=alp*alp*pdist(P[ord[i]],P[ord[(i+1)%N]]);
            pans[i]={{0,ord[i]}};
            REP(j,M)REP(k,M+1){
                if(k==M){
                    if(chmin(mcost,(ll)alp*(pdist(P[ord[i]],ssp[j])+pdist(ssp[j],P[ord[(i+1)%N]])))){
                        pans[i]={{0,ord[i]},{1,j}};
                    }
                }
                else{
                    if(chmin(mcost,(ll)alp*(pdist(P[ord[i]],ssp[j])+pdist(ssp[k],P[ord[(i+1)%N]]))+pdist(ssp[j],ssp[k]))){
                        pans[i]={{0,ord[i]},{1,j},{1,k}};
                    }
                }
            }
            newcost+=mcost;
            if(i==N-1)
                pans[i].push_back({0,0});
        }
        if(chmin(mincost,newcost)){
            ans=pans;
            ansssp=ssp;
        }
        if(rand()%1000000>exp((newcost-cost)/T)*1e6)
            cost=newcost;
        else{
            if(rx!=0){
                reverse(ord.begin()+r1,ord.begin()+r2);
            }
            else{
                if(ry==0){
                    sss[r1].erase(r2);
                    ssp[r1]=cog(sss[r1]);
                }
                else{
                    sss[r1].insert(r2);
                    ssp[r1]=cog(sss[r1]);
                }
            }
        }  
        if(rcnt%50==0){
            double t=(double)(clock()-start)/CLOCKS_PER_SEC/TL;
            if(t>=1.0)
                break;
            T=pow(T0,(t-0.6)/0.4)*pow(T1,t-0.6);
        }
    }
    if(!DEBUG){
        REP(i,M) cout << ansssp[i].x << " " << ansssp[i].y << endl;
        int szs=0;
        REP(i,N) szs+=ans[i].size();
        cout << szs << endl;
        REP(i,N){
            for(auto [t,r]:ans[i]){
                cout << t+1 << " " << r+1 << endl;
            }
        }
    }
    return mincost;
}

int main(){
    if(!DEBUG){
        start=clock();
        input();
        solve();
    }
    else{
        int t=50;
        ll scoresum=0;
        REP(i,t){
            start=clock();
            input_debug(i);
            ll cost=solve();
            ll score=1e9/(1000+sqrt(cost));
            scoresum+=score;
            cout << score << endl;
        }
        cout << scoresum << endl;
    }
    return 0;
}