#include<cstdio>
#include<algorithm>
using namespace std;

int w[5001],p[5001];
int v[2][10003]={0};

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    int n,g,i,j,k;
    scanf("%d %d",&n,&g);

    for(i=1;i<=n;i++)
        scanf("%d %d",&w[i],&p[i]);

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=g;j++)
        {
            v[1][j]=v[0][j];
            if(j>=w[i])
                if(v[0][j-w[i]]+p[i]>v[1][j])
                    v[1][j]=v[0][j-w[i]]+p[i];
        }
        for(k=1;k<=g;k++)
            v[0][k]=v[1][k];
    }

    printf("%d\n",v[1][g]);

    return 0;
}