include<bits/stdc++.h>

using namespace std;
long long n,m,w[10000],v[10000],f[1000][1000];
void xuli(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m;j++ ){
if( j >= w[i]){
f[i][j] = max(f[i-1][j],f[i-1][j-w[i]] + v[i]);
}else{
f[i][j] = f[i-1][j];
}
}
}
}
void xuat(){
cout<<f[n][m];
}
void khoitao(){
for(int i = 0; i <= n; i++ ){
f[i][0] = 0;
}
for(int i = 0; i <= m; i++ ){
f[0][i] = 0;
}
}
int main(){
freopen("catu.inp","r",stdin);
cin>>n>>m;
for(int i = 1; i<= n; i++){
cin>>w[i]>>v[i];
}
khoitao();
xuli();
xuat();
return 0;
}