#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
//Problema Rucsacului folosind programarea dinamica, link informativ https://www.youtube.com/watch?v=8LusJS5-AGo
#define NMAX 5001
#define GMAX 10001
int N,G, dp[NMAX][GMAX];
vector<pair<int,int> > obiecte;

void rezolva()
{
    for(int j=1; j<= G; ++j)
    {
        if(obiecte[0].second <= j)
            dp[0][j]=obiecte[0].first;
    }
    for(int i=1; i< N; ++i)
    {
        for(int j=1;j<=G;++j)
        {
            if(obiecte[i].second > j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(obiecte[i].first + dp[i-1][j - obiecte[i].second], dp[i-1][j]);
        }
    }
}
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    cin >> N >> G;
    int val,weight;
    for(int i=0;i< N;++i)
    {
        cin>>val >> weight;
        obiecte.push_back(make_pair(val,weight));
    }
    rezolva();
    for(int i = 0; i< N; ++i)
    {
        for(int j = 0; j<= G; ++j)
            cout << dp[i][j] << " ";
        cout<<endl;
    }
    cout << dp[N-1][G];
    return 0;
}