#include <fstream>
 using namespace std;
 #define MXN 5001
 #define MXG 5001
 ifstream fin("rucsac.in");
 ofstream fout("rucsac.out");
 long V[MXG];
 int n,g;
 int w[MXN],p[MXN];
int maxi( int i, int j)
{
    if(i==j)  return V[i];
    else
    {
        int a,b;
        a = maxi(i,(i+j)/2);
        b = maxi((i+j)/2+1,j);
        if(a>b) return a;
        else  return b;
    }
}

 int rucsac()
 {
 int i,j;
 for(i=1;i<=n;i++)
 for(j=g;j>=w[i];j--)
 V[j]=maxi(V[j],V[j-w[i]]+p[i]);

 return V[g];
 }

 int main()
 {
 int i;
 fin>>n>>g;
 for(i=1;i<=n;i++)
 fin>>w[i]>>p[i];
 fout<<rucsac();
 fin.close();
 fout.close();
 return 0;
}