#include <fstream>

#define NMAX 5002
#define MAXG 10002

using namespace std;

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

int c[NMAX],g[NMAX],cmax[MAXG];
bool used[MAXG][NMAX];


int main()
{
    int n,i,j,k,s,gmax;
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
        fin>>g[i]>>c[i];
    for(s=1;s<=gmax;s++)
        cmax[s]=-1;
    cmax[0]=0;
    for(s=1;s<=gmax;s++)
        for(i=1;i<=n;i++)
            if(g[i]<=s && cmax[s-g[i]]!=-1 && !used[s-g[i]][i])
                if(cmax[s]<c[i]+cmax[s-g[i]])
                {
                    cmax[s]=c[i]+cmax[s-g[i]];
                    for(k=1;k<=n;k++)
                        used[s][k]=used[s-g[i]][k];
                    used[s][i]=true;
                }
    fout<<cmax[gmax];
    fin.close();
    fout.close();
    return 0;
}