/*
    Keep It Simple!
*/

#include<stdio.h>

#define Max(a,b) (a>b?a:b)

int n,G,v[5005],g[5005],Final[50050000],W;

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

   scanf("%d%d",&n,&W);
   for(int i=1;i<=n;i++)
   {
     scanf("%d%d",&g[i],&v[i]);
     G += g[i];
   }

   for(int i=1;i<=n;i++)
     for(int j=W; j>=g[i];j--)
       Final[j] = Max(Final[j],Final[j-g[i]]+v[i]);

    printf("%d",Final[W]);
}