#include <stdio.h>
#include <string.h>

#define MN 5001
#define MG 10001

int N, G, i, j;

int W[MN], P[MN];
int old_line_buffer[MG], new_line_buffer[MG];
int *old_line, *new_line;

int max(int x, int y) {
    return x > y ? x : y;
}

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]);
    }

    memset(old_line_buffer, 0, sizeof(old_line));
    old_line = old_line_buffer;
    memset(new_line_buffer, 0, sizeof(new_line));
    new_line = new_line_buffer;
    
    for (i=1;i<=N;i++) {
        for (j=0;j<=G;j++) {
            new_line[j] = old_line[j];
            if (W[i] <= j) {
                new_line[j] = max(new_line[j], old_line[j-W[i]] + P[i]);
            }
        }
        int *tmp = old_line;
        old_line = new_line;
        new_line = tmp;
    }

    printf("%d\n", old_line[G]);

    return 0;
}