n种物品，每种物品有很多个，价值不同，任取几种，每种只能取一个，问最大价值是多少。这题就是在01背包下多加了个循环，会01背包再看这个就很容易明白

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;
int dp[105],A[105][105];
int N,M;
int main()
{
    while(~scanf("%d%d",&N,&M)&&(N+M))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)
                scanf("%d",&A[i][j]);
        for(int i=1;i<=N;i++)
            for(int k=M;k>=1;k--)
                for(int j=1;j<=k;j++)
                    dp[k]=max(dp[k],dp[k-j]+A[i][j]);
        printf("%d\n",dp[M]);
    }
    return 0;
}