#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[NMax][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[i][j] = DP[i-1][j];
                if(W[i]<=j)
                    {
                        DP[i][j] = max(DP[i][j],DP[i-1][j-W[i]] + P[i]);
                    }
            }
}

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

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