#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, T;
    cin >> N >> T;

    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    const int B = 3;
    const int BR = (N + B - 1) / B;
    const int BC = (N + B - 1) / B;

    vector<vector<int>> block_sum(BR, vector<int>(BC, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            block_sum[i / B][j / B] += A[i][j];
        }
    }

    vector<pair<int, int>> cells;
    cells.reserve(N * N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cells.push_back({i, j});
        }
    }
    sort(cells.begin(), cells.end(), [&](const auto &lhs, const auto &rhs) {
        if (A[lhs.first][lhs.second] != A[rhs.first][rhs.second]) {
            return A[lhs.first][lhs.second] > A[rhs.first][rhs.second];
        }
        return lhs < rhs;
    });

    auto start_score = [&](int si, int sj) -> long long {
        bool used[20][20] = {};
        const int di[4] = {-1, 1, 0, 0};
        const int dj[4] = {0, 0, -1, 1};
        long long best = A[si][sj];

        auto dfs = [&](auto &&self, int ci, int cj, int depth, long long sum) -> void {
            best = max(best, sum);
            if (depth == 5) return;
            for (int dir = 0; dir < 4; dir++) {
                int ni = ci + di[dir];
                int nj = cj + dj[dir];
                if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
                if (used[ni][nj]) continue;
                used[ni][nj] = true;
                self(self, ni, nj, depth + 1, sum + A[ni][nj]);
                used[ni][nj] = false;
            }
        };

        used[si][sj] = true;
        dfs(dfs, si, sj, 0, A[si][sj]);
        return best;
    };

    int best_start_i = cells[0].first;
    int best_start_j = cells[0].second;
    long long best_start_val = -1;
    int start_limit = min<int>(40, (int)cells.size());
    for (int k = 0; k < start_limit; k++) {
        int i = cells[k].first;
        int j = cells[k].second;
        long long val = start_score(i, j);
        if (val > best_start_val) {
            best_start_val = val;
            best_start_i = i;
            best_start_j = j;
        }
    }

    auto start_time = chrono::steady_clock::now();
    const double TIME_LIMIT = 1.99;
    auto elapsed = [&]() {
        return chrono::duration<double>(chrono::steady_clock::now() - start_time).count();
    };

    auto block_dist = [&](int bi, int bj, int ti, int tj) {
        return abs(bi - ti) + abs(bj - tj);
    };

    auto best_neighbor_block = [&](int bi, int bj) {
        int best_id = bi * BC + bj;
        int best_sum = -1;
        for (int di = -1; di <= 1; di++) {
            for (int dj = -1; dj <= 1; dj++) {
                if (di == 0 && dj == 0) continue;
                int ni = bi + di;
                int nj = bj + dj;
                if (ni < 0 || ni >= BR || nj < 0 || nj >= BC) continue;
                int id = ni * BC + nj;
                if (block_sum[ni][nj] > best_sum || (block_sum[ni][nj] == best_sum && id < best_id)) {
                    best_sum = block_sum[ni][nj];
                    best_id = id;
                }
            }
        }
        return best_id;
    };

    vector<vector<bool>> visited(N, vector<bool>(N, false));
    vector<pair<int, int>> path;

    int cur_i = best_start_i;
    int cur_j = best_start_j;
    visited[cur_i][cur_j] = true;
    path.push_back({cur_i, cur_j});

    const int di[4] = {-1, 1, 0, 0};
    const int dj[4] = {0, 0, -1, 1};

    while ((int)path.size() < T) {
        double remain_time = TIME_LIMIT - elapsed();
        if (remain_time <= 0.0) break;
        int remain_steps = T - (int)path.size();
        double step_budget = remain_time / max(1, remain_steps);
        auto step_deadline = chrono::steady_clock::now() + chrono::duration<double>(step_budget);

        int curr_bi = cur_i / B;
        int curr_bj = cur_j / B;
        int target_block = best_neighbor_block(curr_bi, curr_bj);
        int ti = target_block / BC;
        int tj = target_block % BC;

        int best_i = -1;
        int best_j = -1;
        long long best_val = numeric_limits<long long>::min();
        int best_first_a = -1;

        auto eval_cell = [&](int i, int j) -> long long {
            int bi = i / B;
            int bj = j / B;
            long long val = 3LL * A[i][j] + 2LL * block_sum[bi][bj];
            val += 2LL * (block_dist(curr_bi, curr_bj, ti, tj) - block_dist(bi, bj, ti, tj));
            return val;
        };

        auto dfs = [&](auto &&self, int ci, int cj, int depth, long long sum, int first_i, int first_j) -> void {
            if (chrono::steady_clock::now() >= step_deadline) return;
            if (depth > 0) {
                if (sum > best_val || (sum == best_val && A[first_i][first_j] > best_first_a)) {
                    best_val = sum;
                    best_i = first_i;
                    best_j = first_j;
                    best_first_a = A[first_i][first_j];
                }
            }
            if (depth == 3) return;

            for (int dir = 0; dir < 4; dir++) {
                int ni = ci + di[dir];
                int nj = cj + dj[dir];
                if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
                if (visited[ni][nj]) continue;
                visited[ni][nj] = true;
                int next_first_i = (depth == 0 ? ni : first_i);
                int next_first_j = (depth == 0 ? nj : first_j);
                self(self, ni, nj, depth + 1, sum + eval_cell(ni, nj), next_first_i, next_first_j);
                visited[ni][nj] = false;
                if (chrono::steady_clock::now() >= step_deadline) return;
            }
        };

        visited[cur_i][cur_j] = true;
        dfs(dfs, cur_i, cur_j, 0, 0, -1, -1);

        if (best_i == -1) break;
        cur_i = best_i;
        cur_j = best_j;
        visited[cur_i][cur_j] = true;
        path.push_back({cur_i, cur_j});
    }

    cout << path.size() << '\n';
    for (const auto &p : path) {
        cout << p.first << ' ' << p.second << '\n';
    }

    return 0;
}