using namespace std;
#include <iostream>
#include <fstream>
#define MAXN 5010
#define MAXG 10010

ofstream fout("rucsac.out");
int N, G, Pmax,W[MAXN], P[MAXN],DP[2][MAXG],lmic;
void Citire()
{
    ifstream fin("rucsac.in");
    fin>>N>>G;
    for(int i = 1; i <= N; ++i)
        fin>>W[i]>>P[i];
}
void Rezolvare()
{
//DP[i][g] - profitul maxim care se poate obtine avand la dispozitie primele i obiecte,folosind un ruscac de greutate g
    for(int i = 1; i <= N; ++i,lmic=1-lmic)
    {
        DP[lmic][0]=0;
        for(int g = 0; g <= G; g++)
        {
            // Mai intai nu punem obiectul i.
            DP[1-lmic][g] = DP[lmic][g];

            // Daca acest obiect duce la o solutie mai buna,
            // se adauga obiectul i la o solutie anterioara.
            if(W[i] <= g)
            DP[1-lmic][g] = max(DP[1-lmic][g], DP[lmic][g - W[i]] + P[i]);
        }
    }
}
void Afisare()
{
// Solutia se va afla in starea D[N][G]
// Profitul maxim care se poate obtine avand la dispozitie //toate cele N obiecte si un rucscac de greutate G
    fout<<DP[lmic][G];
}
int main()
{
    Citire();
    Rezolvare();
    Afisare();
    return 0;
}