#include <fstream>
#include <vector>

using namespace std;

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

#define MAX(a, b) ((a > b) ? (a) : (b))

int v[10005], previ[10005];
vector< int > w, c;

int main()
{
    int n;
    cin >> n;

    int g;
    cin >> g;

    int tmp;
    w.push_back(0);
    c.push_back(0);

    for(int i = 0; i < n; i++) {
        cin >> tmp;
        w.push_back(tmp);
        //cout << w[i];
        cin >> tmp;
        c.push_back(tmp);
    }

    //cout << "OK";

    for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= g; j++) {
        //cout << i << " " << j << endl;
        v[j] = previ[j];

        if(j >= w[i])
            v[j] = MAX(v[j], previ[j-w[i]]+c[i]);

    }
        for(int k = 0; k < 10005; k++)
            previ[k] = v[k];
    }

    cout << v[g];

    return 0;
}