#include <iostream>
#include <fstream>
#define maxn 5001
#define maxg 10001
using namespace std;

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

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

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

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

int main()
{
    read();
    solve();
    fout << optim[linie][g];
    return 0;
}