#include <fstream>

using namespace std;

ifstream cin ("rucsac.in");
ofstream cout ("rucsac.out");
int maxim(int x,int y)
{
 if(x>=y)
 return x;
 else
 return y;
}
int dp[2][10005], profitmax;
int main()	{
  int N,G,w,p;
  cin>>N>>G;
  for(int i=1;i<=N;++i)
  {
   cin>>w>>p;
   for(int j=0;j<=G;++j)
   {
    if(w<=j)
     {
         dp[i % 2][j]=maxim(dp[(i-1) % 2][j],dp[(i-1) % 2][j-w]+p);
     }
     else
     {
      dp[i % 2][j]=dp[(i-1) % 2][j];
     }
   }
  }
  for(int i=0;i<=G;++i)
  {
   if(dp[N % 2][i]>=profitmax)
   profitmax=dp[N % 2][i];
  }
  cout<<profitmax;
}