#include <fstream>
#define DIM 5005
#define INF -0x3f3f3f3f
using namespace std;

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

int N,W[DIM],P[DIM],D[2*DIM],G,sol;
int main(){
    fin>>N>>G;
    for(int i=1;i<=N;i++)
        fin>>W[i]>>P[i];
    for(int i=1;i<=2*DIM-1;i++)
        D[i]=INF;
    for(int i=1;i<=N;i++)
        for(int j=G;j>=0;j--)
            if(D[j]!=INF && j+W[i]<=G)
                if(D[j+W[i]]<D[j]+P[i]){
                    D[j+W[i]]=D[j]+P[i];
                    sol=max(sol,D[j+W[i]]);
                }
    fout<<sol<<"\n";
    fin.close();fout.close();
    return 0;
}