'use strict'

const INF = 900719925474099 // Number.MAX_SAFE_INTEGER / 10;

function Main(input){
	let temp = input.trim().split('\n');
	let temp2 = temp[0].split(' ').map((v)=>parseInt(v));
	let n = temp2.shift();
	let w = temp2.shift();
	let wv = new Array(n);

	for(let i=0;i<n;i++){
		wv[i] = temp[i+1].split(' ').map((v)=>parseInt(v));
	}

	let dp = [...new Array(n+10)].map(()=>(new Array(w + 10).fill(0)));
	
	//渡すDP
	for(let i=0;i<n;i++){
		for(let j=0;j<=w;j++){
			//入れる
			if(j + wv[i][0] <= w){
				dp[i+1][j+wv[i][0]] = Math.max(dp[i+1][j+wv[i][0]], dp[i][j] + wv[i][1]);
			}

			//入れない
			dp[i+1][j] = Math.max(dp[i+1][j],dp[i][j]);

		}
		//console.log(dp);
	}
	console.log(Math.max(...dp[n]));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));
