#include <bits/stdc++.h>
using namespace std;

int n, m; // n为分公司数量，m为设备数量
int a[11][20]; // 每个分公司在获得不同数量设备的盈利
int b[20]; // 当前设备分配方案
int jians[20]; // 最佳设备分配方案
int ans; // 最大盈利

// 深度优先搜索(DFS)函数
void dfs(int zhi, int b[], int qian, int k) {
    // 如果当前盈利超过记录的最大盈利，更新最大盈利和最佳分配方案
    if (qian > ans) {
        ans = qian;
        for (int i = 1; i <= n; i++) {
            jians[i] = b[i];
        }
    }
    // 如果没有剩余设备或已经处理完所有公司，结束递归
    if (zhi == 0) return;
    if (k == 0) return;

    // 尝试给公司k分配从0到zhi的设备数量
    for (int i = m; i >= 0; i--) {
        if (zhi >= i) {
            b[k] = i; // 给第k个公司分配i台设备
            dfs(zhi - i, b, qian + a[k][i], k - 1); // 递归处理剩下的设备和公司
            b[k] = 0; // 回溯
        }
    }
}

int main() {
    // 读取分公司和设备数量
    cin >> n >> m;
    // 读取盈利矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    // 调用DFS进行搜索
    dfs(m, b, 0, n);

    // 输出最大盈利及相应的分配方案
    cout << ans << endl;
    for (int i = 1; i <= n; i++) {
        cout << i << " " << jians[i] << endl;
    }

    return 0;
}