// Implementation by Claude Code - v10_postswap.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <climits>
#include <chrono>
#include <random>
#include <cmath>
using namespace std;

static const int dx[] = {-1, 1, 0, 0};
static const int dy[] = {0, 0, -1, 1};
static const double TIME_BEAM = 0.15;
static const double TIME_SA   = 1.70;
static const int    M_PER_POS = 5;

int N, T;
int A[20][20];
using Path = vector<pair<int,int>>;
using Vis  = bitset<400>;
using Clock = chrono::steady_clock;
using TP    = chrono::time_point<Clock>;

inline int cell(int r,int c){ return r*20+c; }

static TP g_t0;
static double elapsed(){ return chrono::duration<double>(Clock::now()-g_t0).count(); }

int deg(int r,int c,const Vis&vis){
    int cnt=0;
    for(int d=0;d<4;d++){int nr=r+dx[d],nc=c+dy[d];if(nr>=0&&nr<N&&nc>=0&&nc<N&&!vis.test(cell(nr,nc)))cnt++;}
    return cnt;
}

// ---- Greedy ----
pair<int,Path> greedy_full(int sr,int sc,int vw,int dw){
    Vis vis;vis.reset();vis.set(cell(sr,sc));
    Path path={{sr,sc}};int score=A[sr][sc],r=sr,c=sc;
    while((int)path.size()<T){
        int best=INT_MIN,nextr=-1,nextc=-1;
        for(int d=0;d<4;d++){int nr=r+dx[d],nc=c+dy[d];if(nr>=0&&nr<N&&nc>=0&&nc<N&&!vis.test(cell(nr,nc))){int fn=A[nr][nc]*vw-deg(nr,nc,vis)*dw;if(fn>best){best=fn;nextr=nr;nextc=nc;}}}
        if(nextr<0) break;
        vis.set(cell(nextr,nextc));path.push_back({nextr,nextc});score+=A[nextr][nextc];r=nextr;c=nextc;
    }
    return {score,path};
}

pair<int,Path> zigzag_run(){
    Path path;
    for(int i=0;i<N&&(int)path.size()<T;i++){
        if(i%2==0) for(int j=0;j<N&&(int)path.size()<T;j++) path.push_back({i,j});
        else        for(int j=N-1;j>=0&&(int)path.size()<T;j--) path.push_back({i,j});
    }
    int s=0;for(auto&p:path)s+=A[p.first][p.second];return {s,path};
}

// ---- Diversity beam (single full pass) ----
struct BSt{int score;short r,c,parent;Vis visited;};
struct HEnt{int score;short r,c,parent;};

pair<int,Path> diversity_beam(){
    vector<BSt> cur;cur.reserve(N*N);
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){BSt s;s.score=A[i][j];s.r=i;s.c=j;s.parent=-1;s.visited.reset();s.visited.set(cell(i,j));cur.push_back(s);}
    vector<vector<HEnt>> hist(T);
    hist[0].resize(cur.size());
    for(int i=0;i<(int)cur.size();i++) hist[0][i]={cur[i].score,cur[i].r,cur[i].c,-1};
    int bsc=-1,bst=0,bix=0;
    for(int i=0;i<(int)cur.size();i++) if(cur[i].score>bsc){bsc=cur[i].score;bst=0;bix=i;}

    auto prune=[&](vector<BSt>&cands)->vector<BSt>{
        sort(cands.begin(),cands.end(),[](const BSt&a,const BSt&b){if(a.r!=b.r)return a.r<b.r;if(a.c!=b.c)return a.c<b.c;return a.score>b.score;});
        vector<BSt> nxt;nxt.reserve(N*N*M_PER_POS);
        for(int i=0,sz=(int)cands.size();i<sz;){int r=cands[i].r,c=cands[i].c;for(int k=0;k<M_PER_POS&&i<sz&&cands[i].r==r&&cands[i].c==c;k++,i++)nxt.push_back(cands[i]);while(i<sz&&cands[i].r==r&&cands[i].c==c)i++;}
        return nxt;
    };

    vector<BSt> cands;cands.reserve(cur.size()*4);
    for(int step=1;step<T&&elapsed()<TIME_BEAM;step++){
        cands.clear();
        for(int pi=0;pi<(int)cur.size();pi++){const BSt&s=cur[pi];for(int d=0;d<4;d++){int nr=s.r+dx[d],nc=s.c+dy[d];if(nr<0||nr>=N||nc<0||nc>=N||s.visited.test(cell(nr,nc)))continue;BSt ns;ns.score=s.score+A[nr][nc];ns.r=(short)nr;ns.c=(short)nc;ns.parent=(short)pi;ns.visited=s.visited;ns.visited.set(cell(nr,nc));cands.push_back(ns);}}
        if(cands.empty()) break;
        auto nxt=prune(cands);
        hist[step].resize(nxt.size());
        for(int i=0;i<(int)nxt.size();i++) hist[step][i]={nxt[i].score,nxt[i].r,nxt[i].c,nxt[i].parent};
        for(int i=0;i<(int)nxt.size();i++) if(nxt[i].score>bsc){bsc=nxt[i].score;bst=step;bix=i;}
        cur=nxt;
    }
    Path path;for(int cs=bst,ci=bix;cs>=0&&ci>=0;){auto&h=hist[cs][ci];path.push_back({h.r,h.c});ci=h.parent;cs--;}
    reverse(path.begin(),path.end());
    return {bsc,path};
}

// ---- SA helpers ----
int extend_greedy(Path&path,Vis&vis,int r,int c,int target,mt19937&rng,double rp){
    int added=0;
    while((int)path.size()<target){
        vector<pair<int,int>> nbrs;
        for(int d=0;d<4;d++){int nr=r+dx[d],nc=c+dy[d];if(nr>=0&&nr<N&&nc>=0&&nc<N&&!vis.test(cell(nr,nc)))nbrs.push_back({nr,nc});}
        if(nbrs.empty()) break;
        int nextr=nbrs[0].first,nextc=nbrs[0].second;
        if(uniform_real_distribution<double>(0,1)(rng)<rp){
            int total=0;for(auto&q:nbrs)total+=A[q.first][q.second];
            if(total>0){int pick=uniform_int_distribution<int>(0,total-1)(rng),acc=0;for(auto&q:nbrs){acc+=A[q.first][q.second];if(pick<acc){nextr=q.first;nextc=q.second;break;}}}
        } else {
            int best=INT_MIN;nextr=-1;nextc=-1;
            for(auto&q:nbrs){int fn=A[q.first][q.second]*4-deg(q.first,q.second,vis);if(fn>best){best=fn;nextr=q.first;nextc=q.second;}}
        }
        vis.set(cell(nextr,nextc));path.push_back({nextr,nextc});added+=A[nextr][nextc];r=nextr;c=nextc;
    }
    return added;
}

pair<int,Vis> prefix_sv(const Path&path,int cut){
    Vis vis;vis.reset();int s=0;
    for(int k=0;k<cut;k++){vis.set(cell(path[k].first,path[k].second));s+=A[path[k].first][path[k].second];}
    return {s,vis};
}


int batch_midswap(Path&path,Vis&vis,int score){
    bool improved=true; int L=(int)path.size();
    while(improved){improved=false;
        for(int i=1;i<L-1;i++){
            int pr=path[i-1].first,pc=path[i-1].second;
            int nr2=path[i+1].first,nc2=path[i+1].second;
            int cr=path[i].first,cc=path[i].second;
            int best_delta=0,bdr=-1,bdc=-1;
            for(int d=0;d<4;d++){int dr=pr+dx[d],dc=pc+dy[d];
                if(dr<0||dr>=N||dc<0||dc>=N||dr==cr&&dc==cc||vis.test(cell(dr,dc))) continue;
                if(abs(dr-nr2)+abs(dc-nc2)!=1) continue;
                int delta=A[dr][dc]-A[cr][cc];
                if(delta>best_delta){best_delta=delta;bdr=dr;bdc=dc;}
            }
            if(bdr>=0){vis.reset(cell(cr,cc));vis.set(cell(bdr,bdc));path[i]={bdr,bdc};score+=best_delta;improved=true;}
        }
    }
    return score;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>N>>T;for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>A[i][j];
    g_t0=Clock::now();

    // Phase 1: greedy initial
    int best_score=-1;Path best_path;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        for(auto& [vw,dw]:vector<pair<int,int>>{{1,0},{4,1}}){auto[sc,path]=greedy_full(i,j,vw,dw);if(sc>best_score){best_score=sc;best_path=path;}}
    }
    {auto[sc,path]=zigzag_run();if(sc>best_score){best_score=sc;best_path=path;}}

    // Phase 2: diversity beam
    {auto[sc,path]=diversity_beam();if(sc>best_score){best_score=sc;best_path=path;}}

    // Phase 3: SA
    mt19937 rng(42);
    Path cur_path=best_path;int cur_score=best_score;
    double sa_start=elapsed();

    while(elapsed()<sa_start+TIME_SA){
        int L=(int)cur_path.size();if(L==0) break;
        double progress=(elapsed()-sa_start)/TIME_SA;
        double temp=pow(1000.0,1.0-progress);

        double r01=uniform_real_distribution<double>(0,1)(rng);
        int op=(r01<0.45)?0:(r01<0.90)?1:2;
        double rp=(progress<0.5)?0.2:0.4;

        Path work_path=(op==1)?Path(cur_path.rbegin(),cur_path.rend()):cur_path;
        int wL=(int)work_path.size();
        int cut;
        if(op==2) cut=max(1,uniform_int_distribution<int>(1,max(1,wL/5))(rng));
        else{int mk=max(1,(int)(wL*0.6)),xk=wL-1;cut=(mk>=xk)?mk:uniform_int_distribution<int>(mk,xk)(rng);}

        auto[ps,vis]=prefix_sv(work_path,cut);
        Path new_path(work_path.begin(),work_path.begin()+cut);
        int er=work_path[cut-1].first,ec=work_path[cut-1].second;
        int added=extend_greedy(new_path,vis,er,ec,T,rng,(op==2)?0.8:rp);
        int new_score=ps+added;
        if(op==1) reverse(new_path.begin(),new_path.end());

        double delta=new_score-cur_score;
        if(delta>=0||uniform_real_distribution<double>(0,1)(rng)<exp(delta/temp)){
            cur_score=new_score;cur_path=new_path;
            if(cur_score>best_score){best_score=cur_score;best_path=cur_path;}
        }
    }

    // Post-process
    {auto[ps,vis]=prefix_sv(best_path,(int)best_path.size());best_score=batch_midswap(best_path,vis,best_score);}
    cout<<best_path.size()<<"\n";
    for(auto&p:best_path) cout<<p.first<<" "<<p.second<<"\n";
    return 0;
}