#include <iostream>

using namespace std;
int n,m;
int mat[100][100];
int dp[100][100];
pair<int, int> path[100][100];
int rek(int i,int j)
{
    if(i==n-1  && j==n-1)
    {
        path[i][j] = make_pair(i, j);
        return mat[i][j];
    }
    if(dp[i][j]!=-1)
    {
        return dp[i][j];
    }
    int maks=-2e9;
    int desno = -2e9;
    int dole = -2e9;
    if(j+1<m)
    {
        desno = rek(i,j+1)+mat[i][j];
    }
    if(i+1<n)
    {
        dole = rek(i+1,j)+mat[i][j];
    }
    maks = max(desno, dole);
    if(dole > desno) {
        path[i][j] = make_pair(i + 1, j);
    }
    else {
        path[i][j] = make_pair(i, j + 1);
    }
    
    dp[i][j]=maks;
    return maks;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>mat[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            dp[i][j]=-1;
        }
    }
    cout<<rek(0,0) << endl;
    
    for(pair<int, int> at = make_pair(0, 0); at != make_pair(n - 1, m - 1); at = make_pair(path[at.first][at.second].first, path[at.first][at.second].second)) {
        cout << at.first  + 1<< " " << at.second + 1<< endl;
    }
    cout << n << " " << m << endl;
    return 0;
}