#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,g1,i,cw;
int gr[5001],pr[5001],r[5001][10001];

int main()
{
    f>>n>>g1;

    for(i=1;i<=n;i++)
        f>>gr[i]>>pr[i];

    for(i=1;i<=n;i++)
        for(cw=0;cw<=g1;cw++)
        {
            r[i][cw]=r[i-1][cw];
            if(gr[i]<=cw)
                r[i][cw] = max(r[i][cw], r[i-1][cw-gr[i]]+pr[i]);

        }
    for(i=1;i<=n;i++)
    {
        for(int j=0;j<=g1;j++)
            g<<r[i][j]<<" ";
            g<<endl;
    }

    g<<r[n][g1];

    return 0;
}