#include <fstream>
#define maxn 5002
#define maxg 10002
using namespace std;

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

int n, g, gr[maxn], cost[maxn], optim[2][maxg], linie;

void read()
{
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
        fin >> gr[i] >> cost[i];
}

void solve()
{
    for (int i = 1; i <= n; i++, linie = 1 - linie)
        for (int j = 0; j <= g; j++) {
            optim[1 - linie][j] = optim[linie][j];
            if (gr[i] <= j)
                optim[1 - linie][j] = max(optim[1 - linie][j], optim[linie][j - gr[i]] + cost[i]);
        }
}

void write()
{
    fout << optim[linie][g];
}

int main()
{
    read();
    solve();
    write();
    return 0;
}