#include <stdio.h>

#define N_MAX 5000
#define W_MAX 10000

int wOb[N_MAX+1],vOb[N_MAX+1];
int mat[2][W_MAX+1];

int max(int a,int b){//functie care returneaza max
  if(a>b)
    return a;
  else
    return b;
}

int main(){
  int n,w,i,j,l;

  FILE *fin=fopen("rucsac.in","r");

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

  fclose(fin);
  l=0;
  for(i=1;i<=n;i++){
    l=1-l;
    for(j=0;j<=w;j++){
      if(wOb[i]<=j)//aplicam recurenta
        mat[l][j]=max(mat[1-l][j],mat[1-l][j-wOb[i]]+vOb[i]);
      else
        mat[l][j]=mat[1-l][j];
    }
  }

  FILE *fout=fopen("rucsac.out","w");
  fprintf(fout,"%d",mat[l][w]);
  fclose(fout);
  return 0;
}
//recurenta:daca w[i]<=W => m[i,w]=max(m[i-1,w],m[i-1,w-w[i]]+v[i])
//          astfel m[i,w]=m[i-1,w]
//W=greutate maxima;w[]=greutatile obiectelor;v[]=valoarea obiectelor