#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,i,w[5010],p[5010],d[5010][10010],j;
int main()
{
   f>>n>>G;
   for(i=1;i<=n;i++)
   {
       f>>w[i]>>p[i];
   }
    for(i=1;i<=n;i++)
    for(j=0;j<=G;j++)
    {
        if(w[i]<=j)
            d[i][j]=max(d[i-1][j] , d[i-1][j-w[i]] + p[i] ) ;
        else
            d[i][j]=d[i-1][j];
    }
    g<<d[n][G]<<' '<<endl;

}