#include <fstream>
#include <iostream>
using namespace std;

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

long n, g;
long G[10005];
long P[10005];
long V[10005];

int main()
{
    fin >> n >> g;
    for(long i = 1; i <= n; ++i)
        fin >> G[i] >> P[i];

    V[0] = 1;

    for(long i = 1; i <= n; ++i)
    {
        for(long j = g; j >= 1; --j)
        {
            if(j-G[i] != 0)
            {
                if(V[j-G[i]] != 0)
                    if(V[j-G[i]] + P[i] > V[j])
                        V[j] = V[j-G[i]] + P[i];
            }
            else if(V[j]<P[i]) V[j] = P[i];
        }
    }

    long maxx = V[1];
    for(long i = 2; i <= g; ++i)
        maxx = max(maxx, V[i]);

    fout << maxx << ' ';
}