#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
int N, G, i, j, sol;
fin >> N >> G;
int W[5001], P[5001];
int Optim[10001]={0};
for (i=1; i<=N; i++)
    fin >> W[i] >> P[i];
sol=0;
for (i=1; i<=N; i++)
{
    for (j=G-W[i]; j>=0; j--)
    {
        if (Optim[j+W[i]]<Optim[j]+P[i])
        {
            Optim[j+W[i]]=Optim[j]+P[i];
            if (Optim[j+W[i]] > sol)
                sol=Optim[j+W[i]];
        }
    }
}
fout << sol;
return 0;
}