#include<bits/stdc++.h>
using namespace std;
int a[20][20],f[20][20],ans[20][20][20];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
    		int x;
    		cin>>x;
    		a[i][j]=x-j;
	}
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<=j;k++)
				if(f[i][j]<f[i-1][k]+a[i][j-k]){
                	f[i][j]=f[i-1][k]+a[i][j-k];
                	for(int w=1;w<=i-1;w++)ans[i][j][w]=ans[i-1][k][w];
                	ans[i][j][i]=j-k;
            	}
    cout<<f[n][m]<<endl;
    for(int i=1;i<=n;i++)cout<<i<<" "<<ans[n][m][i]<<endl;
}