思路：这个题其实就是一个分组背包问题，每组物品可以选0, 1, … M个设备，求最大盈利值不难，稍微难的是求出具体方案，不过这种题我写多了，很熟悉，只要记录下当前 $f[i][j]$ 这个状态是从哪个物品转移过来的即可，也就是第 $i$ 组物品选了几个设备， $path[i][j] = k$ 表示$i,j$这个状态选了 $k$。

// 分组背包 + 逆推方案
#include <iostream>
#include <cstring>

using namespace std;

const int N = 16;

int f[N][N];
int w[N][N];
int path[N][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]; // 第i个公司分配j台机器时的盈利值
        }
    }

    // 分组背包
    // f[i][j]表示只在前i个公司分配设备，且设备数不超过j的最大盈利值
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= m; j ++) {
            for (int k = 0; k <= m; k ++) { // 从第i组物品中去选，只能选其中一个。设备数k可以为0
                if (j >= k) {
                    if (f[i][j] < f[i - 1][j - k] + w[i][k]) {
                        f[i][j] = f[i - 1][j - k] + w[i][k];
                        path[i][j] = k; // i,j这个状态选了k
                    }
                }
            }
        }
    }

    cout << f[n][m] << endl;

    // 逆推：求出每组选了哪种物品
    int i = n, j = m;
    while (i >= 1 && j >= 0) {
        cout << i << " " << path[i][j] << endl;
        j -= path[i][j];
        i --;
    }

    return 0;
}