#include <bits/stdc++.h>
#define maxn 5000
#define maxg 10000

using namespace std;

typedef struct
{
  int w, p;
}ruc;

ruc v[maxn+5];
int dp[2][maxg+5];

int main ()
{
  ifstream fin ( "rucsac.in" );
  ofstream fout ( "rucsac.out" );

  int n, g;

  fin >> n >> g;

  int i;

  for ( i = 0; i < n; i++ )
    fin >> v[i].w >> v[i].p;

  int ind = 0, j, a, b;

  for ( i = 0; i < n; i++, ind = 1 - ind )
    for ( j = 0; j <= g; j++ )
    {
      a = b = 0;
      if ( i > 0 )
        a = dp[1-ind][j];

      if ( j >= v[i].w )
        b = dp[1-ind][j-v[i].w] + v[i].p;

      dp[ind][j] = max ( a, b );
    }

  fout << dp[1-ind][g];

  fin.close ();
  fout.close ();

  return 0;
}