#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,a[10002],c[10002],d[10002],p;
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];
}