#include <bits/stdc++.h>
using namespace std;

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

long long n, W, dp1[10001], dp2[10001];

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