#include<stdio.h>

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

int main(void) {
  int N, W;

  // input the number of items and the maximum weight
  scanf("%d %d", &N, &W);
  int value[N], weight[N];
  int dp[N+1][W+1];

  // input values and weights
  for(int i = 0; i < N; i++) {
    scanf("%d %d", &value[i], &weight[i]);
  }

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