#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,greut,i,j,maxy,g[5200],p[5200],s[100001];
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&greut);
    for (i=1; i<=n; i++)
        scanf("%d %d ",&g[i],&p[i]);
    memset(s,-1,sizeof(s));
    maxy=0;
    s[0]=0;
    for (i=1; i<=n; i++)
    {
        for (j=maxy; j>=0; j--)
        {
            if (s[j]!=-1&&s[j+g[i]]==-1)s[j+g[i]]=p[i]+s[j];
            else if (s[j]!=-1&&(s[j+g[i]]!=-1&&p[i]+s[j]>s[j+g[i]]))s[j+g[i]]=p[i]+s[j];
        }
        maxy+=g[i];
    }
    maxy=0;
    for (i=1; i<=greut; i++)
        maxy=max(maxy,s[i]);
    printf("%d\n",maxy);
}