#include <fstream>
#include<algorithm>

using namespace std;

ifstream cin ( "rucsac.in" );
ofstream cout ( "rucsac.out" );

int dp[10001][2], w[5001], v[5001];
const int INF = -1e9;

int main()
{
    int n, g, i, crt, inainte, j;

    cin >> n >> g;
    for( i = 1; i <=n ; i ++ )
      cin >> w[i] >> v[i];

    for( i = 0; i <= g; i ++ )
      dp[i][1] = INF;

    dp[ w[1] ][1] = v[1];
    for( i = 2; i <= n; i ++ ) {
      crt = i % 2;
      inainte = ( crt + 1 ) % 2;

      for( j = 0; j <= g; j ++ )
        if( j >= w[i] )
          dp[j][crt] = max( dp[j][inainte], dp[j-w[i]][inainte] + v[i] );
        else
          dp[j][crt] = dp[j][inainte];
    }

    crt = n % 2;
    int ans = dp[0][crt];
    for( i = 1; i <= g; i ++ )
      ans = max( ans, dp[i][crt] );

    cout << ans << '\n';
    return 0;
}