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

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

}

fout<<c[N][G];


return 0;
}