#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int Nmax = 5010;
const int Gmax = 10010;

int w[Nmax], p[Nmax];
int v[2][Gmax];

int main()
{
    int i, j, n, g, ln = 1, lv = 0;
    fin >> n >> g;
    for(i = 1; i <= n; ++i) fin >> w[i] >> p[i];
    for(i = 1; i <= n; ++i)
    {
        for(j = 0; j <= g; ++j)
        {
            v[ln][j] = v[lv][j];
            if(j >= w[i]) if(v[lv][j - w[i]] + p[i] > v[ln][j])
                v[ln][j] = v[lv][j - w[i]] + p[i];
        }
        ln = 1 - ln; lv = 1 - lv;
    }
    fout << v[lv][g] << '\n';
    return 0;
}