#include<iostream> using namespace std; int w[101][101],dp[101][101]; int main(){ while(true){ fill(dp[0],dp[0]+100*100,0); int n,m; cin>>n>>m; if(n==0 && m==0){ exit(0); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>w[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]; for(int k=1;k<=m;k++){ if(j>=w[i][k]){ dp[i][j]=max(dp[i-1][j-k]+w[i][k],dp[i][j]); } } } } cout<<dp[n][m]<<endl; } return 0; }