#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int n, Gmax, c[5001],g[5001], use[10001][5001],cmax[5001];

int main()
{
    int s, i, k ;

    fin>>n>>Gmax;
    for(i=1;i<=n;i++)
        {fin>>g[i];
        fin>>c[i];}

    cmax[0]=0;
    for(i=1;i<=Gmax;i++)
        cmax[i]=-1;

    for(s=1;s<=Gmax;s++)
        for(i=1;i<=n;i++)
            if(g[i]<=s &&cmax[s-g[i]]!=-1 && use[s-g[i]][i]==0)
                if(cmax[s]<cmax[s-g[i]]+c[i])
                {
                    cmax[s]=cmax[s-g[i]]+c[i];
                    for(k=1;k<=n;k++)
                        use[s][k]=use[s-g[k]][k];
                    use[s][i]=1;
                }
    int gata=0;
    for(s=Gmax;s>=0;s--)
        if(cmax[s]!=-1)
            {fout<<cmax[s]; break;}
    fout.close();
    return 0;
}