#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g;
int gr[5001],p[5001],cmax[5001],uz[5001][5001];

void citire();
void pd();
void afisare();

int main()
{
    citire();
    pd();
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    int i;
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>gr[i]>>p[i];
}

void pd()
{
    int i,j,k,s;
    for(k=1;k<=g;k++) cmax[k]=-1;
    for(s=1;s<=g;s++)
        for(i=1;i<=n;i++)
            if(gr[i]<=s && uz[s-gr[i]][i]==0)
                if(p[i]+cmax[s-gr[i]]>cmax[s])
                {
                cmax[s]=p[i]+cmax[s-gr[i]];
                for(j=1;j<=n;j++)
                    uz[s][j]=uz[s-gr[i]][j];
                uz[s][i]=1;
                }
}

void afisare()
{
    fout<<cmax[g];
}