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

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

   out << dp[G][n];
    return 0;
}