#include <iostream>
#include <fstream>
#include <memory.h>

using namespace std;

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

const int NMAX = 5e3 + 100;
const int GMAX = 1e4 + 100;
const int oo = 0x3f3f3f3f;

int N, G, W[NMAX], P[NMAX], DP[GMAX];

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

    memset(DP, -oo, sizeof DP); DP[0] = 0;
    for(int i = 1; i <= N; i++)
        for(int j = G; j >= W[i]; j--)
            DP[j] = max(DP[j], DP[j - W[i]] + P[i]);
    int sol = 0;
    for(int i = G; i; i--)
        sol = max(sol, DP[i]);
    fout << sol;

    return 0;
}