#include <bits/stdc++.h>

using namespace std;
const int N = 11;
const int M = 16;
int n;
int m;
int path[N], res[N];
int w[N][M];
int mx;

// u:第几个公司　s:已经产生的价值 r:剩余的机器数量
void dfs(int u, int s, int r) {
    if (u == n + 1) {
        if (s > mx) {
            mx = s;
            memcpy(res, path, sizeof path);
        }
        return;
    }

    for (int i = 0; i <= r; i++) {
        path[u] = i;
        dfs(u + 1, s + w[u][i], r - i); // 给u号公司分配i个机器
        path[u] = 0;
    }
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> w[i][j];

    dfs(1, 0, m);

    printf("%d\n", mx);
    // 输出最优答案时的路径
    for (int i = 1; i <= n; i++) printf("%d %d\n", i, res[i]);
    return 0;
}