#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

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

int n, G, sol;
int g[5005];
int v[5005];
int d[5005]; /// d[i] = valoarea maxima cu obiecte ce cantaresc i

int main()
{
    fin >> n >> G;

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

    for (int i=1;i<=n;++i)
        d[i] = -1;

    for (int i=1;i<=n;++i)
        for (int j=G-g[i];j>=0;--j)
            /**
                j porneste de la G-g[i] pentru a nu depasi G
            **/
            if (d[j]+1)
                d[j+g[i]] = max(d[j+g[i]], d[j] + v[i]);

    for (int i=1;i<=G;++i)
        sol = max(sol, d[i]);

    cout << sol;
}