#include <fstream>

using namespace std;

int n, G;
int g[5010], v[5010];
int D[2][10002];

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    in>>n>>G;
    for(int i = 1; i <= n; ++i)
        in>>g[i]>>v[i];

    int l=0;
    for(int i = 1; i <= n; ++i, l = 1 - l)
        for(int cw = 0; cw <= G; ++cw)
        {
            // Mai intai nu punem obiectul i.
            D[1-l][cw] = D[l][cw];

            // Daca acest lucru duce la o solutie curenta mai buna, adaugam obiectul i la o solutie anterioara.
            if(g[i] <= cw)
                D[1-l][cw] = max(D[1-l][cw], D[l][cw - g[i]] + v[i]);
        }

    out<<D[l][G];
    out.close();
    in.close();

    return 0;
}