#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,A[5010],C[5010],D[10050];
int main(){
	fin>>n>>g;
	for(int i=1; i<=n; i++) fin>>A[i]>>C[i];
	for(int i=0; i<A[1]; i++) D[i]=0;
	for(int i=A[1]; i<=g; i++) D[i]=C[1];
	for(int i=2; i<=n; i++){
		for(int j=g; j>=0; j--) if(j+A[i]<=g) D[j+A[i]]=max(D[j+A[i]],D[j]+C[i]);
	}
	fout<<D[g];
}