#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define nmax 5001
#define gmax 10001

using namespace std;

int n, g, w[nmax], p[nmax], optim[gmax], sol;
int main(int argc, char const *argv[]) {

  FILE *fin, *fout;

  fin = fopen("rucsac.in", "r");
  fout = fopen("rucsac.out", "w");
  int i, j;

  fscanf(fin, "%d %d\n", &n, &g );

  for(i = 1 ; i <= n ; i++){
    fscanf(fin, "%d %d", &w[i], &p[i]);
  }

  for(i = 1 ; i <= n ; i++){
    for(j = g - w[i] ; j >= 0 ; j--){
      if(optim[j + w[i]] < optim[j] + p[i]){ //daca profitul cu w[i] ar fi mai mare decat fara el atunci se intra in if
        optim[j + w[i]] = optim[j] + p[i];
        if(optim[j + w[i]] > sol){
          sol = optim[j + w[i]];
        }
      }
    }
  }

  fprintf(fout, "%d\n", sol );

  fclose(fout);
  return 0;
}