#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int gr[5005], pr[5005], dp[2][10005];
int G,n;
int main()
{
    in >> n >> G;
    for(int i=1; i<=n; i++)
     in >> gr[i] >> pr[i];

     int line = 0;
    for(int i=1; i<=n; i++)
    {
         line = 1-line;
     for(int j=0; j<=G; j++)
     {
          dp[1-line][j] = dp[line][j];
          if( gr[i] <= j)
               dp[1-line][j] = max(dp[1-line][j], dp[line][j-gr[i]]+pr[i]);
     }
    }



  out << dp[1-line][G];


    return 0;
}