#include <stdio.h>

int weight[5001], profit[5001];
int res[10001];
int n, w;

int max(int a, int b) {
  return (a > b) ? a : b;
}

int main() {

  FILE *fr = fopen("rucsac.in", "r");
  FILE *fw = fopen("rucsac.out", "w");

  fscanf(fr, "%d %d", &n, &w);

  for(int i = 1; i <= n; i++)
    fscanf(fr, "%d %d", weight + i, profit + i);

  for(int i = 1; i <= n; i++) {

    for(int j = w - weight[i]; j >= 0; j--) {
      res[j + weight[i]] = max(res[j + weight[i]], res[j] + profit[i]);
    }
  }

  fprintf(fw, "%d", res[w]);

  return 0;
}