#include <fstream>
using namespace std;

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

const int NMax = 5005, GMax = 10005;

int N,G,P[NMax],W[NMax];
int DP[2][GMax];

void Read()
{
    fin>>N>>G;
    for(int i = 1; i<=N; ++i)
        {
            fin>>W[i]>>P[i];
        }
}


void Solve()
{
    for(int i = 1; i<=N; i++)
    {
        for(int j = 1; j<=G; j++)
            {
                DP[1][j] = DP[0][j];
                if(W[i]<=j)
                    {
                        DP[1][j] = max(DP[1][j],DP[0][j-W[i]] + P[i]);
                    }
            }
        for(int j = 1; j<=G; j++)
            DP[0][j] = DP[1][j];
    }

}

void Print()
{
    fout<<DP[1][G]<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}