#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,gr;
bool f;
int gp[10000],pr[10000],d[10000][2];
int main(){
	fin >> n;
	fin >> gr;
	for (int i=1;i<=n;i++){
		fin >> gp[i];
		fin >> pr[i];
	}
	//for (int i=0;i<=gr;i++) d[0][i]=0;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=gr;j++){
			if (gp[f]<=j) d[f][j]=max(d[!f][j],d[!f][j-gp[f]]+pr[f]);
			else d[f][j]=d[!f][j];
			f=!f;
		}
	}
	fout << d[!f][gr];
	return 0;
}


/*
6 12
4 10
2 20
7 15
6 30
4 80
5 25
*/