//他人のソースをJSに焼きなおしただけ版
function Main(input){
  //パラメータ受け取り
  input = input.split("\n");
  inputStr = input[0].split(" ");
  var N = Number.parseInt(inputStr[0]);
  var W = Number.parseInt(inputStr[1]);
  var IM = [];
  for(var i=0 ; i<N ; i++){
    inputStr = input[i+1].split(" ");
    IM.push(inputStr.map( inputStr => parseInt(inputStr)));
  }
  //DP用の器を作る。今回は2次元配列。
  dp = [];
  for(var i=0 ; i<W+1 ; i++){
    dp.push( Array(N+1).fill(0));
  }
  //DPを組む
  var ans = 0;
  for(var i=0 ; i<N ; i++){
    for(var j=0; j<=W ; j++){
      var wt = IM[i][0];  //重量を格納
      var vl = IM[i][1];  //価値を格納

      if( wt<=j ){
        dp[j][i+1] = Math.max(dp[j][i], dp[j-wt][i] + vl);
      } else {
        dp[j][i+1] = dp[j][i];
      }
      //回答の格納
      if( dp[j][i+1] > ans){
        ans = dp[j][i+1];
      }
    }
    console.log(dp);
  }
  //結果表示
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
