#include<bits/stdc++.h>

#define maxn 5001
#define maxg 10001

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");


int greutate[maxn], profit[maxn];
int optim[maxg];
int N,G;


void read()
{
    in>>N>>G;
    for(int i=0; i<N; i++)
        in>>greutate[i]>>profit[i];
}

int dp()
{
    optim[0] = 0;
    int sol = 0;

    for( int i = 1; i <= N; i++)
    {
        for( int j = G - greutate[i]; j >= 0; j--)
        {
            if(optim[j+greutate[i]] < optim[j] + profit[i] )
            {
                optim[j+greutate[i]] = optim[j] + profit[i];
                if( optim[j+greutate[i]] > sol)
                    sol = optim[j+greutate[i]];
            }
        }
    }
    return sol;


}

int main()
{
    read();
    out<<dp()<<endl;
    return 0;
}