#include<iostream>
using namespace std;
int n,m,p[110][110],dp[110][110],ans[110][110],b[110];
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>p[i][j];
		}
	}
	for(int i=1; i<=n; i++) {
		dp[i][0]=0;
	}
	for(int j=1; j<=m; j++) {
		dp[0][j]=0;
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			for(int k=0; k<=j; k++) {
				int x=dp[i][j];
				dp[i][j]=max(dp[i][j],dp[i-1][j-k]+p[i][k]);
				if(x<dp[i][j]) {
					ans[i][j]=max(ans[i][j],k);
				}
			}
		}
	}
	cout<<dp[n][m];
	int x=m;
	for(int i=n; i>=1; i--) {
		b[i]=ans[i][x];
		x-=ans[i][x];
	}
	for(int i=1; i<=n; i++) {
		cout<<"\n"<<i<<" "<<b[i];
	}
	return 0;
}