#include <iostream>

int dp[5001][10001] = {0};

int main()
{
    int N,G;
    std::cin>>N>>G;

    for(int i=1; i<=N; i++)
    {
        int w,p;
        std::cin>>w>>p;

        for(int g=0; g<w; g++)
        {

            dp[i][g]=dp[i-1][g];
        }
        for(int g=w; g<=G; g++)
        {
            dp[i][g]=std::max(dp[i-1][g],dp[i-1][g-w]+p);
        }
    }
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<G; j++)
            std::cout<<dp[i][j]<<" ";
        std::cout<<'\n';
    }
    std::cout<<dp[N][G];
    return 0;
}