#include <stdio.h>


int max(int a, int b,int c){
  if(a>b && a > c){
    return a;
  }else if(b > c && b > a){
    return b;
  }else{
    return c;
  }
}

int main(){
  int i,j;
  int v[110],w[110],dp[110][10010];
  int N,W;
  scanf("%d %d",&N,&W);

  for(i = 1; i <= N ; i++){
    scanf("%d %d",&v[i],&w[i]);
  }
  for(i = 0; i <= W ; i++){
    dp[0][i] = 0;
  }

  for(i = 1; i <= N; i++){
    for(j = 0; j <= W ; j++){
      if(j >= w[i]){
	dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i],dp[i][j-w[i]]+v[i]);
      }else{
	dp[i][j] = dp[i-1][j];
      }
    }
   
  }
  printf("%d\n",dp[N][W]);


  return 0;
}

