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

#define MAXN 5001
#define MAXG 20001

typedef struct {
    int value;
    int weight;
} obiect;

obiect v[MAXN];
int dp[MAXG] = {0};

int main(void) {
    int n, g;

    FILE *fin = fopen("rucsac.in", "r");
    if (fin == NULL) {
        fprintf(stderr, "Eroare la deschidere\n");
        return 1;
    }

    FILE *fout = fopen("rucsac.out", "w");
    if (fout == NULL) {
        fprintf(stderr, "Eroare la deschidere\n");
        fclose(fin);
        return 1;
    }

    fscanf(fin, "%d %d", &n, &g);
    for (int i = 0; i < n; i++) {
        fscanf(fin, "%d %d", &v[i].weight, &v[i].value);
    }

    for (int i = 0; i < n; i++) {
        for (int j = g; j >= v[i].weight; j--) {
            if (dp[j] < dp[j - v[i].weight] + v[i].value) {
                dp[j] = dp[j - v[i].weight] + v[i].value;
            }
        }
    }

    fprintf(fout, "%d\n", dp[g]);

    fclose(fin);
    fclose(fout);
    return 0;
}