#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<math.h>

#define MAX 1001
#define MAX_C 100001
#define max(a,b) ((a>b)?a:b)

int C, N, c[MAX], v[MAX], i, j, dp[MAX_C];

int main() {
  scanf("%d %d",&N,&C);
  assert( N < MAX );
  assert( C < MAX_C );
  for(i=0;i<N;i++) scanf("%d %d",v+i,c+i);
  
  memset(dp,-1,sizeof dp);
  dp[0] = 0;
  /*
    // 01 Knapsack
  for(i=0;i<N;++i) {
    for(j=C;j>=0;--j) if( dp[j] != -1 ) {
      if( j + c[i] <= C ) {
	dp[j+c[i]] = max(dp[j+c[i]],dp[j]+v[i]);
      }
    }
  }
  */
  // Knapsack
  for(i=0;i<N;++i) {
    for(j=0;j<C;++j) if( dp[j] != -1 ) {
	if( j+c[i] <= C ) {
	  dp[j+c[i]] = max(dp[j+c[i]],dp[j]+v[i]);
	}
      }
  }

  int maxi = 0;
  for(i=0;i<=C;i++) maxi = max(maxi,dp[i]);
  printf("%d\n",maxi);
  
  return 0;
}