#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n;
int castig[5005];
int w;
int greutate[5005];
int vect[10005];

int main()
{
    fin>>n>>w;
    for(long i=1;i<=n;++i) fin>>greutate[i]>>castig[i];

    for(long i=0;i<=w;++i)
        {
         if(i<greutate[1]) vect[i]=0;
          else vect[i]=castig[1];
        }

    for(long i=2;i<=n;++i)
        {
         if(greutate[i]<=w)
            {
             for(long j=w;j>=0;j--)
                {
                 if( j >= greutate[i] && castig[i]+vect[j-greutate[i]] > vect[j] )
                     vect[j]=castig[i]+vect[j-greutate[i]];
                }
            }
        }
    fout<<vect[w]<<"\n";
    return 0;
}