#include <cstdio>
#include <algorithm>
#define Nmax 5001
#define Maxg 10001

using namespace std;
int n,gmax,c[Nmax],g[Nmax],cmax[Maxg],uz[Maxg][Nmax],s,i,k;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    /// citesc datele
    scanf("%d %d",&n,&gmax);
    for(i=1;i<=n;i++)
    scanf("%d %d",&g[i],&c[i]);

    /// rezolvarea relatiei de recurenta
    // initializez vectorul de costuri cu -1
    for(s=1;s<=gmax;s++) cmax[s]=-1;
    for(s=1;s<=gmax;s++)
    for(i=1;i<=n;i++)
    {
        if((g[i]<=s) && (cmax[s-g[i]]!=-1) && (!uz[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++)
                uz[s][k]=uz[s-g[i]][k];
                uz[s][i]=1;
            }
        }

    }

    /// afisez rezultatul
    printf("%d",cmax[gmax]);
    return 0;
}