'use strict';
console.log(function(args){
  const tmp = args.trim().split('\n').map( r=>r.split(' ').map(v=>v|0) );
  const N = tmp[0][0], W = tmp[0][1];
  const dp = [Array(W+1).fill(0)];
  for ( let i = 0; i < N; i++ ) {
    let w = tmp[i+1][0];
    let v = tmp[i+1][1];
    dp.push(Array(W+1).fill(0));
    for ( let j = 0; j <= W; j++ ) {
      if ( j >= w ) dp[i+1][j] = Math.max( dp[i][j], dp[i][j-w] + v );
      else dp[i+1][j] = dp[i][j];
    }
  }
  return dp[N][W].toString();
}(require('fs').readFileSync('/dev/stdin', 'utf8')));
