'use strict'

const main = input => {
	const args = input.split('\n').map(arg => arg.split(' '))
	const N = parseInt(args[0][0], 10)
	const W = parseInt(args[0][1], 10)
	const w = new Array()
	const v = new Array()

	for (let i = 1; i <= N; i++) {
		w.push(parseInt(args[i][0], 10))
		v.push(parseInt(args[i][1], 10))
	}

	const dp = new Array(N + 1)

	for (let i = 0; i < dp.length; i++) {
		dp[i] = new Array(W + 1).fill(0)
	}

	for (let i = 0; i < N; i++) {
		for (let j = 0; j <= W; j++) {
			if (j - w[i] >= 0) {
				dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
			}

			dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j])
		}
	}

	console.log(dp[N][W])
}

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