#include <fstream>
#include <vector>
#include <queue>

using namespace std;


int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
         
    int N, G, w, p;
    cin >> N >> G;
   
   vector<int> W, P, laststate(G + 1, 0), newstate(G + 1, 0);

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

       cin >> w >> p;
       W.push_back(w);
       P.push_back(p);
   }

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

       for(int g = 0; g <= G; ++g){

           newstate[g] = laststate[g];
           if(W[i] <= g && newstate[g] < laststate[g - W[i]] + P[i])
            newstate[g] = laststate[g - W[i]] + P[i];
       }
       laststate.swap(newstate);
   }

   cout << laststate[G];

    cin.close();
    cout.close();

    return 0;
}