#include<stdio.h>
int w[5001];
int p[5001];
int dp[10001];
int main()
{
 int n,g,i,j;
 FILE *fin=fopen("rucsac.in","r");
 FILE *fout=fopen("rucsac.out","w");
 fscanf(fin,"%d%d",&n,&g);
 for(i=1;i<=n;i++)
    {
     fscanf(fin,"%d%d",&w[i],&p[i]);
    }
 for(i=1;i<=n;i++)
    {
     for(j=g;j>=w[i];j--)
        {
         if(dp[j]<dp[j-w[i]]+p[i])
            {
             dp[j]=dp[j-w[i]]+p[i];
            }
        }
    }
 fprintf(fout,"%d\n",dp[g]);
 fclose(fin);
 fclose(fout);
return 0;
}