#include<stdio.h>
#define MAX 100001

int max(int a,int b){
 if(a>b)return a;

return b;
}



void func(int N,int W,int v[],int w[]){
int X[MAX]={0};
int i,j;

for(i=0;i<N;i++){

 for(j=1;j<=W;j++){
   if(j>=w[i])X[j]=max(X[j],X[j-w[i]]+v[i]);
 }

}/*たて*/

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

return;
}

int main(){
int N,W;
int v[MAX];
int w[MAX];
int i;

scanf("%d %d",&N,&W);

for(i=0;i<N;i++)scanf("%d %d",&v[i],&w[i]);

func(N,W,v,w);

return 0;
}
