#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 20;
int a[N][M];
int f[N][M];// 前i个公司共分配m台设备最大盈利
int n, m;

void print(int i, int j) {
	if (i == 0)
		return ;

	for (int k = 0; k <= j; k ++) {
		if (f[i - 1][j - k] + a[i][k] == f[i][j]) {
			print(i - 1, j - k);
			printf("%d %d\n", i, k);
			return ;
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			scanf("%d", &a[i][j]);

	for (int i = 1; i <= m; i ++)
		f[1][i] = a[1][i];

	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= m; j ++)
			for (int k = 0; k <= j; k ++)
				f[i][j] = max(f[i][j], f[i - 1][j - k] + a[i][k]);

   printf("%d\n", f[n][m]);

   print(n , m);

	return 0;
}