#include <stdio.h>
int main(void){
      int N,W,dp[100][10000],weight[100],value[100],i,a,b;
      weight[0]=0;
      value[0]=0;
      scanf(" %d %d",&N,&W);
      for(i=1;i<=N;i++){
          scanf(" %d %d",&a,&b);
          value[i]=a;
          weight[i]=b;
      };
      
    
    for(a=1;a<=N;a++){
        for(b=0;b<=W;b++){
            if(weight[a]<=b){
                if(dp[a-1][b]<=(value[a]+dp[a-1][b-weight[a]])){
                    dp[a][b]=(value[a]+dp[a-1][b-weight[a]]);}
                    else{
                    dp[a][b]=dp[a-1][b];};
                }else{
                    dp[a][b]=dp[a-1][b];
                };
        };
    };
    printf("%d\n",dp[N][W]);
    return 0;
}

