#include <iostream>
#include <vector>
#include <utility>
#include <cmath>

double edge_weight(std::pair<int, int> a, std::pair<int, int> b) {
    return std::sqrt(std::pow(a.first - b.first, 2) + std::pow(a.second - b.second, 2));
}

double kruskal(int ver_num, std::vector<std::pair<double, std::pair<int, int>>>& edges) {
    size_t edge_num = edges.size();
    std::sort(std::begin(edges), std::end(edges));
    std::vector<int> treeId(ver_num);
    for (int32_t i = 0; i < ver_num; i++) {
        treeId[i] = i;
    }
    double mstCost = 0;
    std::vector<std::pair<int, std::pair<int, int>>> edgesInMST;
    for (int i = 0; i < edge_num; i++) {
        int firstVer = edges[i].second.first, secVer = edges[i].second.second;
        double cost = edges[i].first;
        if (treeId[firstVer] != treeId[secVer]) {
            edgesInMST.emplace_back(std::make_pair(cost, std::make_pair(firstVer, secVer)));
            mstCost += cost;
            int oldTree = treeId[firstVer];
            for (int j = 0; j < ver_num; ++j) {
                if (treeId[j] == oldTree)
                    treeId[j] = treeId[secVer];
            }
        }
    }
    return mstCost;
}

int main() {
    int num_terminal, num_extra;
    std::cin >> num_terminal >> num_extra;
    std::vector<std::pair<int, int> > vertices(num_terminal);
    std::vector<std::pair<int, int> > added_vertices;
    std::vector<std::pair<double, std::pair<int, int> > > edges;
    for (int i = 0; i != num_terminal; ++i) {
        std::cin >> vertices[i].first >> vertices[i].second;
    }
    int right = -1;
    int down = 100000;
    int up = -1;
    int left = 100000;
    for (int j = 0; j != num_terminal; ++j) {
        if (right < vertices[j].first) {
            right = vertices[j].first;
        }
        if (down > vertices[j].second) {
            down = vertices[j].second;
        }
        if (up < vertices[j].second) {
            up = vertices[j].second;
        }
        if (left > vertices[j].first) {
            left = vertices[j].first;
        }
    }
    std::cout << "OKI\n";
    for (int i = 0; i != num_terminal; ++i) {
        for (int j = i + 1; j < num_terminal; ++j) {
            edges.emplace_back(std::make_pair(edge_weight(vertices[i], vertices[j]), std::make_pair(i, j)));
        }
    }
    double best_mst = kruskal(num_terminal, edges);
    std::cout << best_mst << "\n";
    int new_num_vert = num_terminal;
    int step1 = 1;
    int step2 = 1;
    if (right - left >= 1000) {
        step1 = (right - left) / 300;
    }
    if (up - down >= 1000) {
        step2 = (up - down) / 400;
    }
    std::cout << right << "\n";
    for (int i = down; i < up; i += step1) {
        for (int j = left; j < right && num_extra != 0; j += step2) {
            std::vector<std::pair<double, std::pair<int, int> > > copy_edges = edges;
            std::pair<int, int> possible_vert = std::make_pair(i, j);
            for(int k = 0; k != new_num_vert; ++k) {
                copy_edges.push_back(std::make_pair(edge_weight(possible_vert, vertices[k]), std::make_pair(k, new_num_vert)));
            }
            double loc_mst = kruskal(new_num_vert + 1, copy_edges);
            if (j == 9 && i == 1) {
                std::cout << loc_mst << "\n";
            }
            if (loc_mst < best_mst) {
                best_mst = loc_mst;
                edges = copy_edges;
                --num_extra;
                ++new_num_vert;
                vertices.push_back(possible_vert);
                added_vertices.push_back(possible_vert);
            }
        }
    }
    std::cout << added_vertices.size() << "\n";
    for (auto x : added_vertices) {
        std::cout << x.first << " " << x.second << "\n";
    }
    return 0;
}