#include<bits/stdc++.h>
using namespace std;
const int N=20;
int f[N][N],w[N][N];
int way[N];
int main()
{
	int n,m;
	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=m;j>=0;j--) //枚举体积
		{
			for(int k=0;k<=j;k++) //枚举选择
			{
				f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
			}
		}
	}
	cout<<f[n][m]<<endl; //最大收益
	int k=m;
	for(int i=n;i>=1;i--) //倒着枚举
	{
		for(int j=0;j<=m;j++) //枚举前面占有的体积
		{
			if(f[i][m]==f[i-1][j]+w[i][m-j]) //可以由前面得到
			{
				way[i]=m-j; //记录选择
				m=j; //更新体积
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)
		cout<<i<<" "<<way[i]<<endl;
	return 0;
}