#include <iostream>
#include <cstdio>
using namespace std;
int w[5010],p[5010];
int g[10010];
int main()
{   int n,i,j,G,s=-1;
     g[0]=0;
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    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=G-w[i];j>=0;j--)
       g[j+w[i]]=max(g[j+w[i]],g[j]+p[i]);

printf("%d",g[G]);

    return 0;
}