区间DP：

#include<bits/stdc++.h>
using namespace std;
int f[101][101],graph[101][101],path[101][101][101],n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin>>graph[i][j];
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)    
            for(int k=0;k<=j;k++)
            {
                if (f[i][j]<f[i-1][k]+graph[i][j-k])
                {
                    f[i][j]=f[i-1][k]+graph[i][j-k];
                    for(int h=1;h<i;h++) path[i][j][h]=path[i-1][k][h];
                    path[i][j][i]=j-k;//因为改为了“不给”第i家公司k台机器，所以必须如此调整
                }
            }
    cout<<f[n][m]<<endl;
    for(int i=1;i<=n;i++) cout<<i<<" "<<path[n][m][i]<<endl;
    return 0;
}