#include <iostream>
#include <fstream>
#include <climits>

using namespace std;
int b[1000][1000];
int c[1000][1000];//costul optim pentru traseul care incepe de acolo
int n;
int m;

ifstream fin("data.in");

class Point{
public:
    int x, y;
    void setLocation(int x_, int y_)
    {
        x = x_;
        y = y_;
    }
};

void citire()
{
    fin >> n;
    fin >> m;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
            fin >> b[i][j];
    }
}

int get(int l, int col)
{
    if (l < 0 || l >= n)
        return INT_MIN;
    if (col < 0 || col >= m)
        return INT_MIN;
    return c[l][col];
}

int max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    citire();
    for (int i = 0; i < n; ++i)
        c[i][m - 1] = b[i][m - 1];

    for (int col = m - 2; col >= 0; --col)
    {
        for (int lin = 0; lin < n; ++lin)
        {
            c[lin][col] = b[lin][col] + max(get(lin - 1, col + 1), get(lin + 1, col + 1));
            c[lin][col] = max(c[lin][col], b[lin][col] + get(lin, col + 1));
        }
    }
    cout <<"M-AM PRAJIT \n";
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << c[i][j] << " ";
        cout << endl << "RAU";
    }

    bool unic = true;
    int maxVal = -1;
    Point p;
    for (int l = 0; l < n; ++l)
    {
        if (c[l][0] > maxVal)
        {
            maxVal = c[l][0];
            p.x = l;
        }
        else
            if (c[l][0] == maxVal)
                unic = false;
    }
    cout << maxVal << endl;
    //cout << p.x + 1 << " " << p.y + 1 << endl;
    for (int col = 0; col < m - 1; ++col)
    {
        int ne = get(p.x - 1, col + 1);
        int e = get(p.x, col + 1);
        int se = get(p.x + 1, col + 1);

        if (ne == e || ne == se || e == se)
        {
            unic = false;
        }
        if (ne > e)
        {
            p.setLocation(p.x - 1, col + 1);
        }
        else if (e > se)
        {
            p.setLocation(p.x, col + 1);
        }
        else
        {
            p.setLocation(p.x + 1, col + 1);
        }
        cout << p.x + 1 << " " << p.y + 1;
    }

    if (unic)
    {
        cout << "traseu unic";
    }
}