#include <fstream>
#define INF 11000000

using namespace std;

int f[10010];
int g[5005], c[5005];

int n, i, j, G, sol;

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

    fin>>n>>G;
    for (i=1;i<=n;i++) {
        fin>>g[i]>>c[i];
    }

    for (i=1;i<=G;i++)
        f[i] = -INF;
    f[0] = 0;

    for (i=1;i<=n;i++) {
        for (j=G;j>=0;j--)
            if (f[j] != -INF)
                if (j + g[i] <= G) {
                    f[j + g[i]] = max ( f[j + g[i]], f[j] + c[i] );
                    sol = max(sol, f[j + g[i]]);
                }
    }

    fout<<sol;
    return 0;
}