#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,i,w[5000],p[5000],first[10000],last[1000],j,k;
int main()
{
   f>>n>>G;
   for(i=1;i<=n;i++)
   {
       f>>w[i]>>p[i];
   }
   for(i=1;i<=n;i++)
   {
       for(j=0;j<=G;j++)
    {
        if(w[i]<=j)
            last[j]=max(first[j] , first[j-w[i]] + p[i] ) ;
        else
            last[j]=first[j];
    }
    for(k=0;k<=G;k++) first[k]=last[k];
   }

    g<<first[G]<<' '<<endl;
}