#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(i==0){
D[i][j]=0;
} else {
if(i>0 && j<W[i]){
D[i][j]=D[i-1][j];
} else {
if(i>0 && j>=W[i]){
D[i][j]=max(D[i-1][j], D[i-1][j-W[i]]+P[i]);
}
}
}
}
}
}
void afisare(){
o<<D[N-1][G-1];
}
int main(){
citire();
solve();
afisare();
}