function Main(input) {
  input = input.split("\n");
  const changeInt = (n) => {
    return parseInt(n, 10);
  };
  const [N,W] = input[0].split(' ').map(changeInt);
  const wv = [];
  for (var i = 0; i < N; i++) {
    wv.push(input[i + 1].split(' ').map(changeInt));
  }
 console.log(knapsack(N,W,wv));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

function knapsack(N,W,wv) {
  const dp = Array(N+1).fill(0).map( n =>Array(W+1).fill(0) );
  for (var i = 0; i < N; i++) {
    for (w = 0; w <= W; w++) {
      if (w >= wv[i][0]) {
        dp[i+1][w] = Math.max(dp[i][w - wv[i][0]] + wv[i][1],dp[i][w]);
      } else {
        dp[i+1][w] = dp[i][w];
      }
    }
  }
  return dp[N][W];
}
