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

#define MAX 100
#define MAXG 100

int n, g, w[MAX + 1], p[MAX + 1], d[MAX + 1][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++) {
            d[num][weight] = d[num - 1][weight];

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

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", d[n][g]);

    fclose(in);
    fclose(out);

    return 0;
}