#include <cstdio>
#include <algorithm>
using namespace std;
int d[2][10001],w[5001],p[5001],n,i,j,gm,c1,c2;
int main()
    {
        freopen("rucsac.in","r",stdin);
        freopen("rucsac.out","w",stdout);
        scanf("%d%d",&n,&gm);
        for (i=1 ;i<=n ;i++)
                scanf("%d%d",&w[i],&p[i]);
        for (i=1;i<=n;i++)
        {
            c1=i%2;
            c2=(i+1)%2;
            for (j=1;j<=gm;j++)
                 {
                     d[c1][j]=d[c2][j];
                     if (w[i]<=j)
                         d[c1][j]=max(d[c1][j],d[c2][j-w[i]]+p[i]);
                 }
        }
        printf("%d",d[n%2][gm]);

    }