#include <iostream> using namespace std; int f[20],n,m,w[20][20],ans[20][20],out[20]; int main() { int i,j,k; bool flag; cin>>n>>m; for (i=1;i<=n;++i) { for (j=1;j<=m;++j) { cin>>w[i][j]; } } for (i=1;i<=n;++i) { for (j=m;j>=0;--j) { flag=true; //flag用来标识当前f(i,j)的最大值是否为k=0时取的，因为倒序枚举的话不能算k=0的情况，否则f[j-k]+w[i][k]==f[j]必定满足，ans里面就全是0了；但如果是k≠0时f(i,j)同样可以取到最大值，就没有取到字典序最小 for (k=j;k>0;--k) { if (flag&&f[j-k]+w[i][k]>=f[j]||f[j-k]+w[i][k]>f[j]) { flag=false; f[j]=f[j-k]+w[i][k]; ans[i][j]=k; } } } } cout<<f[m]; for (i=n,j=m;i>0;--i) { out[i]=ans[i][j]; //将结果保存在out数组里 j-=ans[i][j]; } for (i=1;i<=n;++i) { cout<<endl<<i<<" "<<out[i]; //正序输出 } return 0; }