"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const W = parseInt(arg[0].split(" ")[1]);
 
    const items = arg.slice(1, N + 1).map(n=>n.split(" ").map(l=>parseInt(l)));
    
    /*    
    let dp = [...Array(N+1)].map(n=>[...Array(W+1)].fill(0));

    for(let i=1; i<N+1; i++) {
        const w = wv[i-1][0];
        const v = wv[i-1][1];
        
        for(let j=0; j<W+1; j++) {
            if(w > j) {
                // 単体で重さオーバーなら前回のを引き継ぐ
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], v + dp[i-1][j - w]);
            }
        }
    }
    
    console.log(dp[N][W]);
    */
    
    let dp = [...Array(N+1)].map(n=>[...Array(W+1)].fill(0));
    
      var result = 0;
  for(var i=0;i<N;i++){
    for(var w=0;w<=W;w++){
 
      var weight = items[i][0]
      var value = items[i][1]
 
      if(weight <= w){
        dp[w][i+1] = Math.max(dp[w][i], dp[w-weight][i] + value);
      }else{
        dp[w][i+1] = dp[w][i];
      }
 
      if(dp[w][i+1] > result){result = dp[w][i+1];}
 
    }
  }
 
  console.log(result);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));