#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream o("rucsac.out");
int W[10001], P[10001];
int D[10001][10001];
int N, G;
void citire(){
f>>N>>G;
for(int i=0;i<N;i++){
f>>W[i]>>P[i];
}
}
void solve(){
for(int i=0;i<N;i++){
for(int j=0;j<=G;j++){
if(j<W[i+1]){
D[i+1][j]=D[i][j];
} else {
D[i+1][j]=max(D[i][j], D[i][j-W[i]]+P[i+1]);
}
}
}
}
void afisare(){
o<<D[N][G];
}
int main(){
citire();
solve();
afisare();
}