#include <iostream>
#include<fstream>
using namespace std;
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int m[5000], c[5000], a[20000], d[20000];
    int n, G,i,max=0,k;
    f>>n>>G;
   for(i=1; i<=n; i++)
       f>>m[i]>>c[i];
   for(i=1; i<=2*G; i++) a[i]=d[i]=0;
   a[m[1]]=c[1];
   for(k=2; k<=n; k++)
   {
    for(i=1; i<=G; i++)
    {
        if(a[i+m[k]]<a[i]+c[k]) d[m[k]+i]=a[i]+c[k];
        else d[i+m[k]]=a[i+m[k]];
    }
    for(i=1; i<=G;i++)
        a[i]=d[i];
   }
   for(i=1; i<=G; i++)
   {
       if(d[i]>max) max=d[i];
   }
    g<<max;m[5000], c[5000],
    g.close();
}