#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[2][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=w[i]; g<=G; g++){


    c[1][g]=max(c[0][g], c[0][g-w[i]]+p[i] );
 }

for(int g=0; g<=G; g++){c[0][g]=c[1][g];}


}

fout<<c[1][G];


return 0;
}