#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

fstream fin("rucsac.in", ios::in), fout("rucsac.out", ios::out);

int n , G, w[5001], p[5001];
int A[5001][10001];

int main()
{
    fin >> n >> G;
    for(int i = 1 ; i <= n ; i ++)
        fin >> w[i] >> p[i];
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= G ; j++)
            if(w[i] > j)
                A[i][j] = A[i-1][j];
            else
                A[i][j] = max(A[i-1][j], A[i-1][j-w[i]] + p[i]);
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= G ; j++)
            cout << A[i][j] << " ";
        cout << endl;
    }        
    fout << A[n][G];
    return 0;
}