#include <cstdio>

using namespace std;
#define N 1002
#define GMAX 100001
int w[N],p[N];
int D[N][GMAX],n,G,pMax;
int max(int a,int b)
{
    return ((a<b)? b:a);
}
FILE *f=freopen("rucsac.in","r",stdin),*g=freopen("rucsac.out","w",stdout);
int main()
{
    scanf("%d%d",&n,&G);
    int i,j;
    //cITIRE
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&w[i],&p[i]);
    }
    //Obtinem profit maxim pt D[i][j]-i elem la suma de greutate j
   for(i=0;i<n;++i)
        for(j=0;j<=G;++j)
            if(w[i+1]>j)
                D[i+1][j]=D[i][j];
            else {
                D[i+1][j]=max(D[i][j],D[i][j-w[i+1]]+p[i+1]);
            }
        //solutia se afla la n obiecte cu greutate G
    printf("%d\n",D[n][G]);
}