#include <fstream>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;

#define MAXN 5010
#define MAXG 10100

int d[2][MAXG], n, g;
vector<pair<int, int> > obj;

int main()
{
    fstream fin("rucsac.in", ios::in);
    fstream fout("rucsac.out", ios::out);

    fin >> n >> g;
    obj.resize(n);

    for (int i = 0; i < n; ++i) {
        fin >> obj[i].first >> obj[i].second;
    }

    for (int i = 0; i < n; ++i) {
        for (int w = 0; w <= g; ++w) {
            d[1][w] = d[0][w];

            if (w >= obj[i].first) {
                d[1][w] = max(d[1][w], d[0][w - obj[i].first] + obj[i].second);
            }
        }

        memcpy (d[0], d[1], MAXG * sizeof(int));
    }

    fout << d[0][g] << endl;

    fin.close();
    fout.close();
    return 0;
}