#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, greutate;
int dp[5005][10005];

struct rucs
{
    int pret;
    int gr;
}a[5005];

void dinam()
{
    for(int i=1; i<=n; i++) {
        for (int j = 0; j < a[i].gr; j++)
            dp[i][j] = dp[i - 1][j];
        for (int j = a[i].gr; j <= greutate; j++)
        {
             dp[i][j]=max(dp[i-1][j] , dp[i-1][j-a[i].gr] + a[i].pret);
        }
    }
}

int main()
{
    fin >> n >> greutate;
    for(int i=1; i<=n; i++)
       fin >> a[i].gr>> a[i].pret;
    dinam();
    for(int i=1; i<=n; i++, cout <<"\n")
        for(int j=1; j<=greutate; j++)
        cout << dp[i][j] << " ";
    fout << dp[n][greutate];
    return 0;
}