#include <iostream>
#include<fstream>
using namespace std;ifstream fin("rucsac.in");ofstream fout("rucsac.out");
int v[10001],n,m,i,j,p,g,mmax;
int main()
{fin>>n>>m;for(i=1;i<=n;i++){
    fin>>g>>p;for(j=m-g;j>=0;j--){
        if(v[j]+p>v[j+g])v[j+g]=v[j]+p;
        if(mmax<v[j+g])mmax=v[j+g];
    }
    for(j=0;j<=m;j++)cout<<v[j]<<' ';cout<<'\n';
}fout<<mmax;

    return 0;
}