#include <cstdio>

#define MAXN 5010
#define MAXG 10010

int n, g;
int w[MAXN], p[MAXN], best[MAXG];

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d%d", &n, &g);
    for(int i = 1; i <= n; ++i)
        scanf("%d %d", &w[i], &p[i]);
    for(int i=1;i<=n;i++)
        for(int cw=g-w[i];cw>=0;cw--)
        if(best[cw+w[i]]<best[cw]+p[i])
            best[cw+w[i]]=best[cw]+p[i];
    printf("%d\n",best[g]);
    return 0;
}