#include<bits/stdc++.h> using namespace std; inline int read() { int num=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())num=num*10+c-'0'; return num; }//快读 int n,m,f[30][30],value[30][30],maxl; /*以上是变量说明阶段。 f数组：f[i][j]表示前i个公司分j台机器的最大盈利 value数组：value[i][j]表示第i个公司分j台机器的盈利 */ int print(int i,int j) { if(i==0)return 0; for(int k=0;k<=j;k++) //k枚举了前i-1个分公司分得多少机器 if(maxl==f[i-1][k]+value[i][j-k]) //知道结果倒推回去 { maxl=f[i-1][k];//步步为营的方式 print(i-1,k);//继续低柜求解 printf("%d %d\n",i,j-k);//倒序输出 break;//搜到了直接跳出循环 } } int main() { n=read(); m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) value[i][j]=read(); //读入各种数据 for(int i=1;i<=n;i++)//枚举公司数 for(int j=1;j<=m;j++)//枚举机器数（总） { maxl=0; for(int k=0;k<=j;k++)//枚举前i-1个公司分到的机器数 if(f[i-1][k]+value[i][j-k]>maxl) /*f[i-1][k]：前i-1个公司分k台机器的利润 value[i][j-k]：第i个公司分j-k台机器的利润 加起来是i个公司分j台机器的最大利润*/ maxl=f[i-1][k]+value[i][j-k]; f[i][j]=maxl; } printf("%d\n",f[n][m]);//输出结果 print(n,m);//输出分配方案 return 0; }