#include <fstream>
#define ll long long int
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

ll n, W, dp[5001][10001];

int main(){ 
	fin >> n >> W;
	for(int i=1; i<=n; i++){
		ll w, v;
		fin >> w >> v;
		for(int j=1; j<=W; j++){
			dp[i][j] = dp[i - 1][j];
			if(w <= j)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v);
		}
	}
	fout << dp[n][W];
}