#include <fstream>
using namespace std;

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

const int MAXN = 5009;

int N, G, w[MAXN], p[MAXN], profit[MAXN], best;

inline int maxim(int a, int b)
{
    if ( a > b )
        return a;
    return b;
}

int main ()
{
    fin >> N >> G;
    for (int i = 1; i <= N; ++i)
        fin >> w[i] >> p[i];

    for (int i = 1; i <= G; ++i)
        profit[i] = -1;
    profit[0] = 0;

    for (int i = 1; i <= N; ++i)
        for (int j = G - w[i]; j >= 0; --j)
            if ( profit[j] != -1 && profit[j] + p[i] > profit[j + w[i]] )
            {
                profit[j + w[i]] = profit[j] + p[i];
                best = maxim(best, profit[j + w[i]]);
            }

    fout << best;

    fin.close();
    fout.close();

    return 0;
}