#include <cstdio>
#include <utility>
#include <string>
using namespace std;

#define MAXN 1010
#define MAXW 5010
#define INF 1<<30

int main(){

  freopen("energii.in", "r", stdin);
  freopen("energii.out", "w", stdout);

  int N, W, a, b, i, j, minc;
  static int R[MAXN][MAXW];
  pair<int,int> G[MAXN];
  
  scanf("%d%d", &N, &W);
  for(i=1; i<=N; i++){
    scanf("%d%d", &a, &b);
    G[i]=make_pair(a, b);
  }

  memset(R[0], 0, sizeof(R[0]));
  minc=INF;
  
  for(i=1; i<=N; i++){
    R[i][0]=0;
    for(j=1; j<=W; j++){
      if(G[i].first<=j){
	if(G[i].second+R[i-1][j-G[i].first] > R[i-1][j])
	  R[i][j]=G[i].second+R[i-1][j-G[i].first];
	else
	  R[i][j]=R[i-1][j];
      } 
      else {
	R[i][j]=R[i-1][j];
      }
    }
  }

  printf("%d\n", R[N][W]);

  return 0;

}