#include<bits/stdc++.h>
const int maxn=5005;
using namespace std;
long long show(long,long);
long long maxl,f[11][20],value[11][20];
int main(){
    long long m,n,i,j,k;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    cin>>value[i][j];
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
    	maxl=0;
    	for(k=0;k<=j;k++)
    	if(f[i-1][k]+value[i][j-k]>maxl)
    	maxl=f[i-1][k]+value[i][j-k];
    	f[i][j]=maxl;
	}
	cout<<f[n][m]<<endl;
	show(n,m);
    return 0;
}
long long show(long i,long j)
{
	long long k;
	if(i==0) return 0;
	for(k=0;k<=j;k++)
	if(maxl==f[i-1][k]+value[i][j-k])
	{
		maxl=f[i-1][k];
		show(i-1,k);
		cout<<i<<" "<<j-k<<endl;
		break; 
	}
}