#include <fstream>

using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
long long N,G,i,g[10000],p[10000],dp[2000][2000],x,k,j;
int main()
{
     cin>>N>>G;
     for(i=1;i<=N;i++)cin>>g[i]>>p[i];
     for(i=1;i<=N;i++)
        for(j=1;j<=G;j++)dp[i][j]=-1;

     for(i=1;i<=N;i++)
     {
         for(x=1;x<=G;x++)
         {
             if(x-g[i]>=0 && dp[i-1][x-g[i]]!=-1)
             {
                 dp[i][x]=max(dp[i][x],dp[i-1][x-g[i]]+p[i]);
             }

             dp[i][x]=max(dp[i][x],dp[i-1][x]);
         }
     }

     k=0;
     for(i=1;i<=G;i++)
     {
         k=max(k,dp[N][i]);
     }

     cout<<k;





    return 0;
}