# include <cstdio>

using namespace std;

int cost[10005], w[10005], p[10005], max, min, n, G, i, j;
int main()
{
    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--)
        if (cost[j + w[i]] < cost[j] + p[i])
        {
               cost[j + w[i]] = cost[j] + p[i];
               if (cost[j + w[i]] > max) max = cost[j + w[i]];
               }
    
    printf("%d",max);
    
return 0;
}