#include<fstream>

using namespace std;

int w[5001], p[5001];
int a[10001];

int main() {

    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    int n, g, rez = 0;
    in >> n >> g;

    for (int i = 1; i <= n; ++i) {
        in >> w[i] >> p[i];
    }

    a[0] = 0;

    for( int i = 1; i <= n; ++i)
        for( int j = g - w[i]; j >= 0; --j) {
            if(a[j+w[i]] < a[j] + p[i] )
            {
                a[j+w[i]] = a[j] + p[i];
                if(a[j+w[i]] > rez)
                    rez = a[j+w[i]];
            }
        }

    out << rez;
    return 0;
}