C++ :

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

long max1,f[11][20],value[11][20];

//输出各分公司分配情况
int show(int i,int j)                          
{
  int k;
  if (i==0) return 0;
  for (k=0;k<=j;k++)
     //递归求各公司分配的机器数量
     if (max1==f[i-1][k]+value[i][j-k])          
     {
       max1=f[i-1][k];
       show(i-1,k);
       cout<<i<<" "<<j-k<<endl;
       break;
     }
}


int main()
{
  long m,n,i,j,k;
  cin>>n>>m;
  for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
    cin>>value[i][j];
  for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
    { 
      max1=0;
      for (k=0;k<=j;k++)
       if (f[i-1][k]+value[i][j-k]>max1)
          max1=f[i-1][k]+value[i][j-k];
      f[i][j]=max1; 
    } 
   cout<<f[n][m]<<endl;                         //输出最大盈利值
   show(n,m);                                   //输出分配情况
}