//実験３：アドバイスに基づいて再帰で組む
//グローバル変数の定義
var N = 0;
var W = 0;
var obj = [];
var dp = [];
//再帰処理
function RecursiveDp(i,j){

  //メモによる再処理防止
  if (dp[i][j] != 0) {        
    return dp[i][j];
  }

  var res = 0;
  if (i === N) { 
    //商品がもうないので0を代入する        
    res = 0;
  } else if (j < obj[i][0]) { 
    //容量不足なので入れない処理だけをする
    res = RecursiveDp(i+1, j);
  } else { 
    //入れると最大になるとは限らないので入れる時と入れない時の大きい方を取る
    res = Math.max(RecursiveDp(i+1, j), RecursiveDp(i+1,j-obj[i][0])+obj[i][1]);
  }
  dp[i][j] = res;
  return res;
}
function Main(input){
  //パラメータ受け取り
  input = input.split("\n");
  inputStr = input[0].split(" ");
  N = Number.parseInt(inputStr[0]);
  W = Number.parseInt(inputStr[1]);
  //要素の溜め込み
  for(var i=0 ; i<N ; i++){
    inputStr = input[i+1].split(" ");
    obj.push(inputStr.map( inputStr => parseInt(inputStr)))
  }
  //DP用メモの作成
  for(var i=0 ; i<=N ; i++){
    dp.push(Array(W+1).fill(0));
  }
  //再帰しつつ結果を出力
  console.log(RecursiveDp(0,W));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));