#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][20004], m1, m2, nr, r;

int main () {
    
    fin >> n >> g;
    fin >> a >> b;
    rc[1][a] = b;
    x = 1;  y = 2;
    r = g;
    
    for (i = 2; i <= n; i++)
    {
        fin >> a >> b;
        rc[y][a] = b;
        
        
        if (g+a <= r)   g += a;
        else g = r;
        
        for (cw = 1; cw <= g; cw++)
            if (rc[x][cw] != 0 || rc[x][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);
                nr = cw;
            }
        g = nr;
        
        /*for (cw = 1; cw <= g; cw++)
            cout << rc[x][cw] << " ";   cout << "\n";
        for (cw = 1; cw <= g; cw++)
            cout << rc[y][cw] << " ";   cout << "\n";
        cout << "\n";*/
        
        a = x;
        x = y;
        y = a;
    }
    
    fout << rc[2][r] << "\n";
}