实测无需DP,只需DFS即可通过本题

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
#define LL long long
#define pb push_back
#define F(i,a,b) for(int i=a;i<=b;i++)
#define dF(i,b,a) for(int i=b;i>=a;i--)
int n,m,ans,a[N],b[N],w[N][N];
void dfs(int x,int sum)
{
    if(x > n)
    {
        if(sum < m) return;
        int res = 0;
        F(i,1,n) res += w[i][a[i]];
        if(res > ans)
        {
            ans = res;
            F(i,1,n) b[i] = a[i];
        }
        return;
    }
    F(i,0,m)
        if(sum + i <= m)
        {
            a[x] = i;
            dfs(x+1,sum+i);
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    F(i,1,n) F(j,1,m) scanf("%d",&w[i][j]);
    dfs(1,0);
    printf("%d\n",ans);
    F(i,1,n) printf("%d %d\n",i,b[i]);
    return 0;
}