#include <bits/stdc++.h>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii..out");
int n,g;
struct object
{ int w,p; };
object x[5005];
int a[2][1005];
void in()
{
    fin>>n>>g;
    int i;
    for(i=1;i<=n;i+=1)
        fin>>x[i].w>>x[i].p;
}
void calcul()
{
    int i,j;
    int l=1;
    for(i=1;i<=n;i+=1,l^=1)
    {
        for(j=g;j>=1;j-=1)
            if(x[i].w>j)
                a[l][j]=a[l^1][j];
            else
                a[l][j]=max(a[l^1][j],a[l^1][j-x[i].w]+x[i].p);
        for(int k=1;k<=g;k+=1)
            fout<<a[l][k]<<' ';
        fout<<endl;
    }
    l^=1;
    cout<<a[l][g];
}
int main()
{
    in();
    calcul();
    return 0;
}