#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
short w[5001],p[5001];
short n,greutate;
int d[2][5001];
void citire()
{
    f>>n>>greutate;
    for(int i=1;i<=n;++i)
        f>>w[i]>>p[i];
}
int main()
{
    citire();
    int l=0;

    for(int i=1;i<=n;++i,l=1-l)
        for(int cw=0;cw<=greutate;++cw)
            {
                d[1-l][cw]=d[l][cw];
                if(w[i]<=cw)
                    d[1-l][cw]=max(d[1-l][cw],d[l][cw-w[i]]+p[i]);
                for(int i=0;i<2;++i)
                {
                    for(int j=0;j<greutate;++j)
                        cout<<d[i][j]<<" ";
                    cout<<'\n';
                }
                cout<<'\n';
            }
    cout<<d[l][greutate];
    return 0;
}