#include <bits/stdC++.h>
using namespace std;
ifstream fin("rucsac.in")
ofstream fout("rucsac.out")
int n,gr;
int gp[1000],pr[1000],d[1000][1000];
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[i]<=j) d[i][j]=max(d[i-1][j],d[i-1][j-gp[i]]+pr[i]);
			else d[i][j]=d[i-1][j];
		}
	}
	fout << d[n][gr];
	return 0;
}


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