#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

long long i, cw, n, g, a, b, x, y, rc[3][10004], mx, nr, r;
bool bn[3][10004];

int main () {
    
    fin >> n >> g;
    fin >> a >> b;
    rc[1][a] = b;
    x = 1;  y = 2;
    r = g;
    bn[1][a] = 1;
    mx = 0;
    for (i = 2; i <= n; i++)
    {
        fin >> a >> b;
        rc[y][a] = b;
       
        if (g+a <= r)   g += a;
        else g = r;
        
        for (cw = 0; cw <= g; cw++)
        {
            bn[y][cw] = 0;
            if (bn[x][cw] == 1 && (bn[x][cw-a] == 0 || cw-a < 0))
            {
                rc[y][cw] = max(rc[y][cw], rc[x][cw]);
                bn[y][cw] = 1;
                nr = cw;
            }
            
            else if (bn[x][cw] == 0 && bn[x][cw-a] == 1 && cw-a >= 0)
            {
                rc[y][cw] = max(rc[y][cw], rc[x][cw-a]+b);
                bn[y][cw] = 1;
                nr = cw;
            }
            
            else if (bn[x][cw] == 1 && bn[x][cw-a] == 1 && cw-a >= 0)
            {
                if (max(rc[x][cw], rc[x][cw-a]+b) > rc[y][cw])  rc[y][cw] = max(rc[x][cw], rc[x][cw-a]+b);
                bn[y][cw] = 1;
                nr = cw;
            }
            
            if (rc[y][cw] > mx) mx = rc[y][cw];
        }
        bn[y][a] = 1;
        g = nr;

        /*for (cw = 0; cw <= g; cw++)
            cout << bn[x][cw] << " ";   cout << "\n";
        for (cw = 0; cw <= g; cw++)
            cout << rc[x][cw] << " ";   cout << "\n";
        for (cw = 0; cw <= g; cw++)
            cout << rc[y][cw] << " ";   cout << "\n";
        for (cw = 0; cw <= g; cw++)
            cout << bn[y][cw] << " ";   cout << "\n";
        cout << "\n";*/
        
        a = x;
        x = y;
        y = a;
    }

    fout << mx << "\n";
}