#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[5000][10000];
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[i][j] = v[i-1][j];

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

    cout << v[n][g];

    return 0;
}