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