#include <bits/stdc++.h>

   using namespace std;
 
     ifstream fin("rucsac.in");
     ofstream fout("rucsac.out");
 
long long int N, G, pret[5010], greu[5010], F[11000]; 

  int main(){
    fin>>N>>G;
    for(long long int i=1; i<=N; i++)
        fin>>greu[i]>>pret[i];
    for(long long int i=1; i<=N; i++)
        for(long long int j=G; j>=greu[i]; j--)
            F[j] = max( F[j], F[j-greu[i]] + pret[i] );
    fout<<F[G];
    return 0;
}