'use strict';
(function(input){
  input=input.trim().split(/\n/).map(str=>str.split(/\s+/).map(x=>x-0));
  const N=input[0][0];
  const W=input[0][1];
  const dp=[];//dp[i][w]で重さwまでで最初のi個から選ぶときの価値の最大
  for(let i=0;i<=N;i++){
    dp[i]=[];
    for(let w=0;w<=W;w++){
      dp[i][w]=0;
    }
  }
  for(let i=1;i<=N;i++){
    let wi=input[i][0];
    let vi=input[i][1];
    for(let w=0;w<=W;w++){
      dp[i][w]=dp[i-1][w];
      if(w>=wi&&dp[i][w]<(dp[i-1][w-wi]+vi))
        dp[i][w]=dp[i-1][w-wi]+vi;
    }
  }
  //console.log(dp);
  console.log(dp[N][W]);
})(require('fs').readFileSync('/dev/stdin','utf8'));
