#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N,G,p[5005],w[5005],a[10005],b[10005],i,n,j;

int main()
{fin>>N>>G;
 for(i=1;i<=N;i++)
    fin>>w[i]>>p[i];
 for(i=1;i<=N;++i)
    {for(j=1;j<=G;++j)
        {if(w[i]>j)a[j]=b[j];
         else {a[j]=max(b[j],b[j-w[i]]+p[i]);
              }
        }
     for(j=1;j<=G;++j)
        b[j]=a[j];
    }
 fout<<a[G];
}