#include<fstream>
#include<vector>
#include<algorithm>
#define Nmax 5001
#define Gmax 10001
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int W[Nmax], P[Nmax];
int Optim[Gmax];
int main() {
    int n,g;
    f>>n>>g;
    for (int i=1;i<=n;i++) f>>W[i]>>P[i];
    Optim[0]=0;
    int sol=0;
    for( int i=1;i<=n;i++)
        for( int 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]];
            }
        }
    g<<sol;
    return 0;
}