#include<fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
unsigned int gr,n,v[5001],g[5001],a[10001],b[10001];
int main()
{
   fin>>n;
   fin>>gr;

   for(int i=1;i<=n;i++)
   {
       fin>>g[i];
       fin>>v[i];
   }

   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=gr;j++)
       {
           b[j]=max(a[j],v[i]+a[j-g[i]]);

       }
       for(int j=1;j<=gr;j++)
       {
           a[j]=b[j];

       }
   }
   fout<<b[gr-2];
}