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

int n, Gmax, c[5001],g[5001], use[5001][10001],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[i][s-g[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[k][s]=use[k][s-g[i]];
                    use[i][s]=1;
                }
    int gata=0;
    for(s=Gmax;s>=0;s--)
        if(cmax[s]!=-1)
            {fout<<cmax[s]; break;}
    fout.close();
    return 0;
}