#include<bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in"); ofstream fout("rucsac.out");





int N, G, w[5010], p[5010];
long long c[5010][10010];

int main(){
fin>>N>>G;

for(int i=1; i<=N; i++){
    fin>>w[i]>>p[i];
}



for(int i=1; i<=N; i++){

 for(int g=0; g<=G; g++){
        if( (g-w[i])<0 ){c[i][g]=c[i-1][g];}
        else{
    c[i][g]=max(c[i-1][g], c[i-1][g-w[i]]+p[i] );}
 }




}

fout<<c[N][G];


return 0;
}