#include <stdio.h>

#define max(a, b) (a > b ? a : b)

struct Item {
  int weight;
  int value;
};

int dp[105][10005];
int main(void) {
  int n;
  int W;
  struct Item items[105];
  scanf("%d %d", &n, &W);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &items[i].value, &items[i].weight);
  }

  for (int i = 0; i < n; i++) {
    for (int w = 0; w <= W; w++) {
      if (items[i].weight <= w) {
        dp[i + 1][w] = max(dp[i][w], dp[i][w - items[i].weight] + items[i].value);
      }
      else {
        dp[i + 1][w] = dp[i][w];
      }
    }
  }

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

  return (0);
}

