"use strict";

function main(input){
  const args = input.trim().split('\n').map(_=>_.split(' ').map(_=>parseInt(_,10)));
  const n = args[0][0];
  const w = args[0][1];
  const items = args.slice(1);
  
  const dp = Array(w+1).fill(0); // 容量をi使うときの最大価値
  for(let i=0; i<n; i++){
    const weight = items[i][0];
    const value = items[i][1];
    for(let k=w; k>=weight; k--){
      dp[k] = Math.max(dp[k-weight] + value, dp[k]);
    }
  }
  
  console.log(dp.reduce((acc,cur)=>Math.max(acc,cur)));
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));  