#include <bits/stdc++.h>
using namespace std;
int main(){
ifstream fin("rucsac.in");ofstream fout("rucsac.out");
long int n,g;
fin>>n>>g;
long int v[n];long int w[n];
for(long int a=0;a<n;a++){
    fin>>w[a]>>v[a];
}
int long k[g+1];memset(k,0,sizeof(k));
for(int i=0;i<n;i++){
    for(int j=g;j>=w[i];j--){
        k[j]=max(k[j],v[i]+k[j-w[i]]);
    }
}
fout<<k[g];

}