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