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

     for( int i=1; i<=n; i++)
          for( int j = G; j>0; j--)
               if( gr[i] <=j)
               dp[j] = max( dp[j], dp[j-gr[i]] + c[i]);
     out << dp[G];


    return 0;
}