#include <iostream.h>
#include <stdlib.h>

int comb[30];
int table[50][30];
int m,n;
int maxpoints;
int ans[30];

int count()
{
    int c=0,i;
    for(i=0;i<n;i++)
    {
        if(comb[i]==0) continue;
        c+=table[comb[i]-1][i];
    }
    return c;
}

void partition(int sum, int no,int p)
{
    if(no==1)
    {
        comb[p]=sum;
        int i;

        int points=count();
        if(points>maxpoints)
        {
           maxpoints=points;
           for(i=0;i<n;i++)
                ans[i]=comb[i];
        }
    }

    if(no>1)
    {
        int i;
        for(i=0;i<=sum;i++)
        {
            comb[p]=i;
            partition(sum-i,no-1,p+1);
        }
    }
}


int main()
{
    int i,j;
    cin >> m >> n;

    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            cin >> table[i][j];

    partition(m,n,0);

    cout << maxpoints << endl;
    for(i=0;i<n;i++)
        cout << i+1 << " " << ans[i] << endl;

}