//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

ll N,T;
ll A [20][20];

void input(){
    cin>>N>>T;
    rep(i,N)rep(j,N)cin>>A[i][j];
}

// =========================================================
// 焼きなまし法による単純パス最大化
// =========================================================

mt19937 rng(20260502);
const int dx4[4] = {-1, 1, 0, 0};
const int dy4[4] = {0, 0, -1, 1};

inline bool in_bounds(int x, int y) {
    return 0 <= x && x < N && 0 <= y && y < N;
}
inline bool adj(const P& a, const P& b) {
    return abs((int)(a.first - b.first)) + abs((int)(a.second - b.second)) == 1;
}

vector<P> path;
bool used[20][20];
ll score_cur = 0;

vector<P> best_path;
ll best_score = LLONG_MIN;

inline void push_cell(int x, int y) {
    path.emplace_back(x, y);
    used[x][y] = true;
    score_cur += A[x][y];
}
inline void pop_cell() {
    auto [x, y] = path.back();
    used[x][y] = false;
    score_cur -= A[x][y];
    path.pop_back();
}
void clear_path() {
    for (auto [x, y] : path) used[x][y] = false;
    path.clear();
    score_cur = 0;
}

// 末尾からランダムウォークで延伸（長さ max_len まで or 行き詰まりまで）
void extend_random(int max_len) {
    while ((int)path.size() < max_len) {
        auto [x, y] = path.back();
        int nxs[4], nys[4], cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx4[k], ny = y + dy4[k];
            if (in_bounds(nx, ny) && !used[nx][ny]) {
                nxs[cnt] = nx; nys[cnt] = ny; cnt++;
            }
        }
        if (cnt == 0) break;
        int c = rng() % cnt;
        push_cell(nxs[c], nys[c]);
    }
}

// =========================================================
// Greedy 初期解:
//   1) 5x5 ブロック 16 個を蛇行順に巡る Hamiltonian (400 セル) を構築
//      (各ブロックは entry/exit 固定で 5x5 上の DFS により Hamiltonian を生成)
//   2) snake 上の position 順に上位 T/2 個のアンカーを並べる
//   3) 先頭から順に未訪問セル経由で BFS 連結し、長さ T を超えたら打切り
//   4) 余り分は末尾ランダムウォークで延伸
// =========================================================

// ブロック 16 個分の (entry_r, entry_c, exit_r, exit_c) (グローバル座標)
// 並びは serpentine: (0,0)(0,1)(0,2)(0,3) → (1,3)(1,2)(1,1)(1,0) → (2,*) → (3,*)
const int BLOCK_DATA[16][4] = {
    { 0, 0,  4, 4},  // (0,0)
    { 4, 5,  0, 9},  // (0,1)
    { 0,10,  4,14},  // (0,2)
    { 4,15,  4,19},  // (0,3) 折り返し下へ
    { 5,19,  9,15},  // (1,3)
    { 9,14,  5,10},  // (1,2)
    { 5, 9,  9, 5},  // (1,1)
    { 9, 4,  9, 0},  // (1,0) 折り返し下へ
    {10, 0, 14, 4},  // (2,0)
    {14, 5, 10, 9},  // (2,1)
    {10,10, 14,14},  // (2,2)
    {14,15, 14,19},  // (2,3) 折り返し下へ
    {15,19, 19,15},  // (3,3)
    {19,14, 15,10},  // (3,2)
    {15, 9, 19, 5},  // (3,1)
    {19, 4, 15, 0},  // (3,0) 終端
};
const int BLOCK_TL[16][2] = {
    { 0, 0},{ 0, 5},{ 0,10},{ 0,15},
    { 5,15},{ 5,10},{ 5, 5},{ 5, 0},
    {10, 0},{10, 5},{10,10},{10,15},
    {15,15},{15,10},{15, 5},{15, 0},
};

bool dfs_vis[5][5];
vector<P> dfs_buf;

bool dfs_block(int r, int c, int r0, int c0, int tr, int tc, int visited) {
    dfs_vis[r - r0][c - c0] = true;
    dfs_buf.push_back(P(r, c));
    if (visited == 25) {
        if (r == tr && c == tc) return true;
        dfs_vis[r - r0][c - c0] = false;
        dfs_buf.pop_back();
        return false;
    }
    // 枝刈り: 残り歩数で目的地に到達できるか (Manhattan + パリティ)
    int steps_left = 25 - visited;
    int dist = abs(r - tr) + abs(c - tc);
    if (dist > steps_left || ((steps_left - dist) & 1)) {
        dfs_vis[r - r0][c - c0] = false;
        dfs_buf.pop_back();
        return false;
    }
    for (int k = 0; k < 4; k++) {
        int nr = r + dx4[k], nc = c + dy4[k];
        int br = nr - r0, bc = nc - c0;
        if (br < 0 || br >= 5 || bc < 0 || bc >= 5) continue;
        if (dfs_vis[br][bc]) continue;
        if (dfs_block(nr, nc, r0, c0, tr, tc, visited + 1)) return true;
    }
    dfs_vis[r - r0][c - c0] = false;
    dfs_buf.pop_back();
    return false;
}

// 16 ブロックを連結した 400 セルの蛇行 Hamiltonian
vector<P> build_snake_of_snakes() {
    vector<P> snake;
    snake.reserve(400);
    for (int idx = 0; idx < 16; idx++) {
        int sr = BLOCK_DATA[idx][0], sc = BLOCK_DATA[idx][1];
        int er = BLOCK_DATA[idx][2], ec = BLOCK_DATA[idx][3];
        int r0 = BLOCK_TL[idx][0], c0 = BLOCK_TL[idx][1];
        memset(dfs_vis, 0, sizeof(dfs_vis));
        dfs_buf.clear();
        if (!dfs_block(sr, sc, r0, c0, er, ec, 1)) {
            cerr << "[snake] block " << idx << " ham not found" << endl;
            return {};
        }
        for (auto p : dfs_buf) snake.push_back(p);
    }
    // 隣接性チェック (デバッグ)
    for (int i = 1; i < (int)snake.size(); i++) {
        if (!adj(snake[i - 1], snake[i])) {
            cerr << "[snake] non-adjacent at " << i << ": "
                 << snake[i-1].first << "," << snake[i-1].second << " -> "
                 << snake[i].first << "," << snake[i].second << endl;
            return {};
        }
    }
    return snake;
}

// BFS 最短路: (sx,sy) から (tx,ty) へ、used を回避 (始点は除外)。
// 経路 (両端含む) を返す。到達不能なら空。
vector<P> bfs_shortest(int sx, int sy, int tx, int ty) {
    static int dist[20][20];
    static int prev_dir[20][20];
    rep(i, 20) rep(j, 20) { dist[i][j] = -1; prev_dir[i][j] = -1; }
    queue<P> q;
    dist[sx][sy] = 0;
    q.push(P(sx, sy));
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == tx && y == ty) break;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx4[k], ny = y + dy4[k];
            if (!in_bounds(nx, ny)) continue;
            if (dist[nx][ny] != -1) continue;
            if (used[nx][ny]) continue;
            dist[nx][ny] = dist[x][y] + 1;
            prev_dir[nx][ny] = k;
            q.push(P(nx, ny));
        }
    }
    if (dist[tx][ty] == -1) return {};
    vector<P> p;
    int cx = tx, cy = ty;
    while (!(cx == sx && cy == sy)) {
        p.emplace_back(cx, cy);
        int k = prev_dir[cx][cy];
        cx -= dx4[k]; cy -= dy4[k];
    }
    p.emplace_back(sx, sy);
    reverse(p.begin(), p.end());
    return p;
}

// 1 つの snake (block 巡回順) でアンカー貪欲を実行し、(score, path) を返す。
// fwd/bwd の両方向を試して良い方を採用。
pair<ll, vector<P>> greedy_with_snake(const vector<P>& snake,
                                       const vector<P>& top_cells) {
    int snake_pos[20][20];
    rep(i, 20) rep(j, 20) snake_pos[i][j] = -1;
    for (int i = 0; i < (int)snake.size(); i++) {
        snake_pos[snake[i].first][snake[i].second] = i;
    }
    vector<P> anchors = top_cells;
    sort(anchors.begin(), anchors.end(),
         [&](const P& a, const P& b) {
             return snake_pos[a.first][a.second] < snake_pos[b.first][b.second];
         });

    auto build = [&](const vector<P>& seq) -> pair<ll, vector<P>> {
        clear_path();
        if (seq.empty()) return {LLONG_MIN, {}};
        push_cell(seq[0].first, seq[0].second);
        for (int i = 1; i < (int)seq.size(); i++) {
            int ax = seq[i].first, ay = seq[i].second;
            if (used[ax][ay]) continue;
            auto& tail = path.back();
            vector<P> seg = bfs_shortest(tail.first, tail.second, ax, ay);
            if (seg.empty()) continue;
            if ((ll)path.size() + (ll)seg.size() - 1 > T) break;
            for (int k = 1; k < (int)seg.size(); k++) {
                push_cell(seg[k].first, seg[k].second);
            }
        }
        extend_random((int)T);
        return {score_cur, path};
    };
    vector<P> rev_anchors(anchors.rbegin(), anchors.rend());
    auto fwd = build(anchors);
    auto bwd = build(rev_anchors);
    return (fwd.first >= bwd.first) ? fwd : bwd;
}

void greedy_initial_solution() {
    // 基準 snake (左上→右優先) を構築し、対称変換で 4 変種を生成
    vector<P> s0 = build_snake_of_snakes();
    assert((int)s0.size() == 400);
    vector<vector<P>> snakes(4);
    snakes[0] = s0;                                       // 左上, 行優先
    snakes[1].reserve(400);                               // 左上, 列優先 (転置)
    snakes[2].reserve(400);                               // 右上, 行優先 (左右反転)
    snakes[3].reserve(400);                               // 右上, 列優先 (転置+左右反転)
    for (auto [r, c] : s0) {
        snakes[1].emplace_back(c, r);
        snakes[2].emplace_back(r, 19 - c);
        snakes[3].emplace_back(c, 19 - r);
    }
    const char* variant_name[4] = {
        "TL-row", "TL-col", "TR-row", "TR-col",
    };

    // 上位 T/2 個の高価値マス
    vector<pair<ll, P>> all_cells;
    rep(i, N) rep(j, N) all_cells.push_back({A[i][j], P(i, j)});
    sort(all_cells.begin(), all_cells.end(),
         [](const auto& a, const auto& b) { return a.first > b.first; });
    int top_k = max(1, (int)(T / 2));
    if (top_k > (int)all_cells.size()) top_k = all_cells.size();
    vector<P> top_cells;
    for (int i = 0; i < top_k; i++) top_cells.push_back(all_cells[i].second);

    // 4 変種を試行
    vector<pair<ll, vector<P>>> results(4);
    for (int v = 0; v < 4; v++) {
        results[v] = greedy_with_snake(snakes[v], top_cells);
    }

    int best_v = 0;
    for (int v = 1; v < 4; v++) {
        if (results[v].first > results[best_v].first) best_v = v;
    }
    auto& chosen = results[best_v];

    clear_path();
    for (auto [x, y] : chosen.second) push_cell(x, y);
    best_path = path;
    best_score = score_cur;

    set<P> anchor_set(top_cells.begin(), top_cells.end());
    int hit = 0;
    for (auto& p : path) if (anchor_set.count(p)) hit++;

    cerr << "[greedy] anchors=" << top_k
         << " hit=" << hit << "/" << top_k
         << " len=" << path.size() << "/" << T
         << " score=" << best_score
         << " variant=" << variant_name[best_v]
         << " (TL-row=" << results[0].first
         << " TL-col=" << results[1].first
         << " TR-row=" << results[2].first
         << " TR-col=" << results[3].first << ")" << endl;
}

// === 近傍 1: 末尾 k 削除 → 再延伸 ===
struct TailMove {
    bool reversed;
    int prefix_len;
    vector<P> popped;
};
bool tr_apply(TailMove& m) {
    int len = path.size();
    if (len < 2) return false;
    m.reversed = (rng() & 1);
    if (m.reversed) reverse(path.begin(), path.end());
    int kmax = min(len - 1, 6);
    int k = 1 + (int)(rng() % kmax);
    m.prefix_len = len - k;
    m.popped.clear();
    m.popped.reserve(k);
    for (int i = 0; i < k; i++) {
        m.popped.push_back(path.back());
        pop_cell();
    }
    extend_random(T);
    return true;
}
void tr_rollback(TailMove& m) {
    while ((int)path.size() > m.prefix_len) pop_cell();
    for (int i = (int)m.popped.size() - 1; i >= 0; i--) {
        push_cell(m.popped[i].first, m.popped[i].second);
    }
    if (m.reversed) reverse(path.begin(), path.end());
}

// === 近傍 2: 挿入（path[i] と path[i+1] の共通隣接セルを差し込む）===
struct InsertMove {
    int pos;
    P cell;
};
bool ins_apply(InsertMove& m) {
    int len = path.size();
    if (len < 2 || len >= T) return false;
    for (int trial = 0; trial < 10; trial++) {
        int i = rng() % (len - 1);
        auto [x1, y1] = path[i];
        auto [x2, y2] = path[i + 1];
        P cands[4]; int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int cx = x1 + dx4[k], cy = y1 + dy4[k];
            if (!in_bounds(cx, cy)) continue;
            if (used[cx][cy]) continue;
            if (abs(cx - x2) + abs(cy - y2) != 1) continue;
            cands[cnt++] = P(cx, cy);
        }
        if (cnt == 0) continue;
        P c = cands[rng() % cnt];
        m.pos = i + 1;
        m.cell = c;
        path.insert(path.begin() + m.pos, c);
        used[c.first][c.second] = true;
        score_cur += A[c.first][c.second];
        return true;
    }
    return false;
}
void ins_rollback(InsertMove& m) {
    used[m.cell.first][m.cell.second] = false;
    score_cur -= A[m.cell.first][m.cell.second];
    path.erase(path.begin() + m.pos);
}

// =========================================================
// 自明な局所改善:
// 連続2手が90度ターンの場合 (path[i-1]→path[i]→path[i+1] が L字)、
// 2x2 ブロックの対角未使用マスの方が高得点なら path[i] と入れ替える。
// 隣接性は両側で維持されるので常に valid。
// =========================================================
int corner_swap_pass() {
    int swaps = 0;
    int len = path.size();
    for (int i = 1; i + 1 < len; i++) {
        auto [r0, c0] = path[i - 1];
        auto [r1, c1] = path[i];
        auto [r2, c2] = path[i + 1];
        int dr1 = r1 - r0, dc1 = c1 - c0;
        int dr2 = r2 - r1, dc2 = c2 - c1;
        // 90度ターンのみ (内積==0 は直角、直進は内積>0、U字は不可)
        if (dr1 * dr2 + dc1 * dc2 != 0) continue;
        int nr = r0 + dr2, nc = c0 + dc2;  // 2x2 の対角マス
        if (!in_bounds(nr, nc)) continue;
        if (used[nr][nc]) continue;
        if (A[nr][nc] <= A[r1][c1]) continue;
        used[r1][c1] = false;
        used[nr][nc] = true;
        score_cur += A[nr][nc] - A[r1][c1];
        path[i] = P(nr, nc);
        swaps++;
    }
    return swaps;
}
int corner_sweep() {
    int total = 0;
    while (true) {
        int s = corner_swap_pass();
        if (s == 0) break;
        total += s;
    }
    return total;
}

// === 近傍 3: 削除（path[i-1] と path[i+1] が隣接していれば path[i] を削除）===
struct DeleteMove {
    int pos;
    P cell;
};
bool del_apply(DeleteMove& m) {
    int len = path.size();
    if (len < 3) return false;
    for (int trial = 0; trial < 10; trial++) {
        int i = 1 + (int)(rng() % (len - 2));
        if (!adj(path[i - 1], path[i + 1])) continue;
        m.pos = i;
        m.cell = path[i];
        used[m.cell.first][m.cell.second] = false;
        score_cur -= A[m.cell.first][m.cell.second];
        path.erase(path.begin() + i);
        return true;
    }
    return false;
}
void del_rollback(DeleteMove& m) {
    path.insert(path.begin() + m.pos, m.cell);
    used[m.cell.first][m.cell.second] = true;
    score_cur += A[m.cell.first][m.cell.second];
}

const double TIME_LIMIT_MS = 1900.0;

inline double elapsed_ms(chrono::steady_clock::time_point st) {
    return chrono::duration<double, milli>(chrono::steady_clock::now() - st).count();
}

int main(){
    input();
    auto start = chrono::steady_clock::now();

    // 温度スケールは A の値域から決める
    ll amax = LLONG_MIN, amin = LLONG_MAX;
    rep(i, N) rep(j, N) { amax = max(amax, A[i][j]); amin = min(amin, A[i][j]); }
    double T_start = max(1.0, (double)(amax - amin));
    double T_end = max(0.1, T_start * 0.001);

    greedy_initial_solution();
    int sw_init = corner_sweep();
    if (score_cur > best_score) { best_score = score_cur; best_path = path; }
    double t_init_ms = elapsed_ms(start);
    ll initial_score = best_score;
    ll corner_swaps = sw_init;

    ll iter = 0, accepted = 0, improved = 0;
    double now_ms = 0;
    while (true) {
        if ((iter & 1023) == 0) {
            now_ms = elapsed_ms(start);
            if (now_ms > TIME_LIMIT_MS) break;
        }
        iter++;

        double progress = now_ms / TIME_LIMIT_MS;
        double temp = T_start * pow(T_end / T_start, progress);

        ll old_score = score_cur;
        int op = rng() % 100;
        bool applied = false;
        TailMove tm; InsertMove im; DeleteMove dm;
        int kind = -1;

        if (op < 60) { applied = tr_apply(tm); kind = 0; }
        else if (op < 80) { applied = ins_apply(im); kind = 1; }
        else              { applied = del_apply(dm); kind = 2; }

        if (!applied) continue;

        ll delta = score_cur - old_score;
        bool accept;
        if (delta >= 0) accept = true;
        else {
            double prob = exp((double)delta / temp);
            double r = (double)(rng() & 0xFFFFFF) / (double)0x1000000;
            accept = r < prob;
        }

        if (accept) {
            accepted++;
            if (score_cur > best_score) {
                improved++;
                int sw = corner_sweep();
                corner_swaps += sw;
                best_score = score_cur;
                best_path = path;
            }
        } else {
            if (kind == 0) tr_rollback(tm);
            else if (kind == 1) ins_rollback(im);
            else del_rollback(dm);
        }
    }

    // 最終 sweep: best 状態を current に復元してから sweep
    clear_path();
    for (auto [x, y] : best_path) push_cell(x, y);
    int sw_final = corner_sweep();
    corner_swaps += sw_final;
    if (score_cur > best_score) { best_score = score_cur; best_path = path; }

    double t_total_ms = elapsed_ms(start);
    double t_sa_ms = t_total_ms - t_init_ms;
    cerr << fixed << setprecision(2);
    cerr << "[time] init=" << t_init_ms << "ms"
         << " sa=" << t_sa_ms << "ms"
         << " total=" << t_total_ms << "ms"
         << " (limit=" << TIME_LIMIT_MS << "ms)" << endl;
    cerr << "[stat] iter=" << iter
         << " iter/s=" << (iter * 1000.0 / max(1.0, t_sa_ms))
         << " accepted=" << accepted
         << " (" << (accepted * 100.0 / max((ll)1, iter)) << "%)"
         << " improved=" << improved << endl;
    cerr << "[score] init=" << initial_score
         << " best=" << best_score
         << " gain=" << (best_score - initial_score)
         << " len=" << best_path.size() << "/" << T
         << " corner_swaps=" << corner_swaps << endl;

    // 出力（フォーマットは問題に合わせて要調整）
    cout << best_path.size() << "\n";
    for (auto [x, y] : best_path) cout << x << " " << y << "\n";

    return 0;
}