#include <fstream>
#include <iostream>
#include <iterator>
#include <algorithm>

#define MAXN 5002
#define MAXG 10002

using namespace std;

int knapsack[MAXG];

int main()
{
    int n, g;
    fstream fin("rucsac.in", fstream::in);
    fstream fout("rucsac.out", fstream::out);
    
    fin >> n >> g;
    //cout << n << " " << g << endl;
    
    for (int i=0; i<n; ++i)
    {
        int w, v;
        fin >> w >> v;
        //cout << vObjs[i].w << " " << vObjs[i].v << endl;
        
        for (int j=g; j>=w; --j)
        {
            if (v + knapsack[j - w] > knapsack[j])
            {
                knapsack[j] = v + knapsack[j - w];
            }
            
            /*int x = v + knapsack[j - w];
            int y = knapsack[j];
            
            knapsack[j] = x - ((x - y) & ((x - y) >> (sizeof(int) * 8 - 1)));*/
        }
    }
    
    fout << knapsack[g] << "\n";
    
    return 0; 
}