// Problema rucsacului.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// Problema rucsacului.
// rc[i][cw] = max(rc[i-1][cw], rc[i-1][cw-W[i]]+P[i]), deci rc[cw] = max(rc[cw], rc[cw-W[i]]+P[i]).

#include <iostream>
#include <fstream>
#pragma warning(disable: 4996)
#define MAXN 5006
#define MAXG 10006
using namespace std;

FILE* fin, * fout;

int N, G;
int W[MAXN], P[MAXN];
int Rucsac[MAXG];

static inline void Read()
{
    fscanf(fin, "%d %d", &N, &G);
    for (int i = 1; i <= N; i++)
        fscanf(fin, "%d %d", &W[i], &P[i]);
}

static inline void Solve()
{
    int sol = -1;
    for(int i=1;i<=N;i++)
        for (int cw = G - W[i]; cw >= 0; cw--)
        {
            Rucsac[cw + W[i]] = max(Rucsac[cw + W[i]], Rucsac[cw] + P[i]);
            sol = max(sol, Rucsac[cw + W[i]]);
        }
    fprintf(fout, "%d", sol);
}

int main()
{
    fin = fopen("rucsac.in", "r");
    fout = fopen("rucsac.out", "w");
    Read();
    Solve();
    fclose(fin);
    fclose(fout);
    return 0;
}