#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXn 5010
#define MAXg 10010
int n, g,w[MAXn], p[MAXn],d[2][MAXg];
int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d%d", &n, &g);
	int l=0,i,cw;
    for(i = 1; i <= n; ++i)
        scanf("%d%d", &w[i], &p[i]);
    for(i = 1; i <= n; ++i, l = 1 - l)
        for(cw = 0; cw <= g; ++cw)
        {
			d[1-l][cw] = d[l][cw];
            if(w[i] <= cw)
                d[1-l][cw] = max(d[1-l][cw], d[l][cw - w[i]] + p[i]);
        }
    printf("%d\n",d[l][g]);
    return 0;
}