#include <stdio.h>

#define MAXN 5001
#define MAXG 10001

int weight[MAXN], profit[MAXN];
int w, n;

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

int rucsac(int w, int n, int weight[], int profit[]) {

  if(n == -1 || w == 0)
    return 0;

  if(weight[n] > w)
    return rucsac(w, n - 1, weight, profit);

  return max(rucsac(w, n - 1, weight, profit) , rucsac(w - weight[n], n - 1, weight, profit) + profit[n]);
}

int main() {

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

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

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

  fprintf(fw, "%d\n", rucsac(w, n - 1, weight, profit));

  return 0;
}