#include<iostream>
#include<fstream>
#define nmax 50001
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N,G,d[nmax],sol=0;

int main ()
{  int i,j,x,y;
   f>>N>>G;  
    for(i=1;i<=N;i++)
    {   f>>x>>y;
        for(j=G-x;j>=0;j--)
        {       if(d[j+x]<d[j]+y)
                d[j+x]=d[j]+y;
                if(d[j+x]>sol)
                sol=d[j+x]; }}
    g<<sol;
    return 0;   
}