#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<ctime>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define TLE (double)clock()/CLOCKS_PER_SEC<=0.95 
#define int long long 
typedef pair<int,int> PII;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int N = 1e2+10;
int n,m;
int w[N][N];
int dp[N][N];
int path[N];
signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>w[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j];
			for(int k=1;k<=j;k++)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]);
			}
		}
	}
	cout<<dp[n][m]<<endl;
	int j=m;
	for(int i=n;i>=1;i--)
	{
		for(int k=0;k<=j;k++)
		{
			if(dp[i][j]==dp[i-1][j-k]+w[i][k])
			{
				path[i]=k;
				j-=k;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)	cout<<i<<" "<<path[i]<<endl;
	return 0;
}