#include <stdio.h>
#include <stdlib.h>

#define MAX 5000
#define MAXG 10000

int n, g, w[MAX + 1], p[MAX + 1], new[MAXG + 1], old[MAXG + 1];

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

void build (void) {
    //prima linie e cu 0-uri
    for (int num = 1; num <= n; num++) {
        for (int weight = 0; weight <= g; weight++) {
            new[weight] = old[weight];

            if (weight >= w[num]) {
                new[weight] = max(new[weight], old[weight - w[num]] + p[num]);
            }
        }

        for (int weight = 0; weight <= g; weight++) {
            old[weight] = new[weight];
        }
    }
}

int main(void) {
    FILE *in, *out;

    if ((in = fopen("rucsac.in", "r")) == NULL) {
        perror("fopen");
        exit(1);
    }
    if ((out = fopen("rucsac.out", "w")) == NULL) {
        perror("fopen");
        exit(1);
    }

    fscanf(in, "%d %d", &n, &g);
    for (int i = 1; i <= n; i++) {
        fscanf(in, "%d %d", &w[i], &p[i]);
    }

    build();

    fprintf(out, "%d", old[g]);

    fclose(in);
    fclose(out);

    return 0;
}