#include <fstream>
using namespace std;

#define dim 10005

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    int gr[dim],val[dim],v[dim]={0};
    int n,c,i,j,a,b,max;

    in>>n>>c;
    for(i=0;i<n;++i) in>>gr[i]>>val[i];

    for(i=0;i<n;++i)
    {
        for(j=c; j>=gr[i]; --j)
        {
            a=v[j-gr[i]] + val[i]; // Potential
            b=v[j]; // Actual pe poz j
            if(a>b) v[j]=a;
        }

        /*for(j=0;j<=c;++j)
        {
            if(v[j]<10) out<<" ";
            out<<v[j]<<" ";
        }
        out<<"\n";*/
    }

    max=0;
    for(i=0;i<=c;++i)
        if(v[i]>max)
            max=v[i];

    out<<max;

    in.close();
    out.close();
    return 0;
}