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

int main(void) {
    FILE *fin = fopen("rucsac.in", "r");
    if (fin == NULL) {
        perror("Eroare la deschiderea fisierului de intrare");
        exit(EXIT_FAILURE);
    }

    int n, g;
    if (fscanf(fin, "%d %d", &n, &g) != 2) {
        fprintf(stderr, "Eroare la citirea datelor initiale.\n");
        fclose(fin);
        exit(EXIT_FAILURE);
    }

    int *dp = (int *)calloc(g + 1, sizeof(int));
    if (dp == NULL) {
        perror("Eroare la alocarea memoriei pentru vectorul DP");
        fclose(fin);
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < n; ++i) {
        int w, p;
        if (fscanf(fin, "%d %d", &w, &p) != 2) {
            fprintf(stderr, "Eroare la citirea obiectului %d.\n", i);
            free(dp);
            fclose(fin);
            exit(EXIT_FAILURE);
        }

        if (w <= g) {
            for (int cw = g; cw >= w; --cw) {
                if (dp[cw - w] + p > dp[cw]) {
                    dp[cw] = dp[cw - w] + p;
                }
            }
        }
    }
    fclose(fin);

    FILE *fout = fopen("rucsac.out", "w");
    if (fout == NULL) {
        perror("Eroare la deschiderea fisierului de iesire");
        free(dp);
        exit(EXIT_FAILURE);
    }

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

    free(dp);
    return 0;
}