

function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0].split(" ")[0]);
  var W = parseInt(input[0].split(" ")[1]);
  var V = new Array(W);
  for(var i=0;i<N+1;i++){
    tmp=new Array(W+1).fill(0);
    V[i]=tmp;
  }
  var w = new Array(N);
  var v = new Array(N);
  for(var i=0;i<N;i++){
    tmp=input[i+1].split(" ");
    w[i] = parseInt(tmp[0]);
    v[i] = parseInt(tmp[1]);
  }
  var ans =0;
  for(var i=1;i<N+1;i++){
    for(var j=0;j<W+1;j++){
      if(w[i-1]<=j){
        V[i][j]=Math.max(V[i-1][j-w[i-1]]+v[i-1],V[i-1][j]);
      }else{
        V[i][j]=V[i-1][j];
      }
      ans=Math.max(ans,V[i][j]);
    }
  }

  console.log('%s', ans);
  return ans;
}
// "実行する"ボタンを押した時に実行される関数 (デバッグ用)
function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));