#include <fstream>
using namespace std;
ofstream fout("rucsac.out");
ifstream fin("rucsac.in");

const int NMAX = 5005;
const int GMAX = 10005;

int W[NMAX], P[NMAX];
int Sol[GMAX];

int main()
{
    int N, G, sol = 0;

    fin >> N >> G;

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

    for(int i=1; i<=N; i++)
        for(int j=G-W[i]; j>=0; j--) {
            if(Sol[j+W[i]] < Sol[j] + P[i]) {
                Sol[j+W[i]] = Sol[j] + P[i];
                if(Sol[j+W[i]] > sol)
                    sol = Sol[j+W[i]];
            }
        }

    fout << sol << '\n';
    return 0;
}