#include <iostream>
#include <fstream>
#define nmax 5005
using namespace std;
int n,mx,i,w[nmax],v[nmax],dp[2][10005],j;
int main()
{
    ifstream f ("rucsac.in");
    ofstream g ("rucsac.out");
    f>>n>>mx;
    for (i=1; i<=n; i++)
        f>>w[i]>>v[i];
    for (i=1; i<=n; i++)
        for (j=1; j<=mx; j++)
        {
            if (i%2==1)
            {
                if (w[i]>j) dp[1][j]=dp[0][j];
                else dp[1][j]=max(dp[0][j],dp[0][j-w[i]]+v[i]);
            }
            else
            {
                if (w[i]>j) dp[1][j]=dp[0][j];
                else dp[0][j]=max(dp[1][j],dp[1][j-w[i]]+v[i]);
            }
        }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=mx; j++)
            cout<<dp[i%2][j]<<' ';
        cout<<'\n';
    }
    int rsp=0;
    for (int i=1; i<=mx; i++)
        rsp=max(rsp,dp[n%2][i]);
    g<<rsp;
}