#include <stdio.h>

#define MAX_OBIECTE 5001
#define MAX_GREUTATE 10001

int greutate[MAX_OBIECTE], valoare[MAX_OBIECTE];
int dp[MAX_GREUTATE];

int main() {
    FILE *fin = fopen("rucsac.in", "r");
    FILE *fout = fopen("rucsac.out", "w");

    int nr_obiecte, capacitate;
    fscanf(fin, "%d %d", &nr_obiecte, &capacitate);

    for (int i = 1; i <= nr_obiecte; ++i) {
        fscanf(fin, "%d %d", &greutate[i], &valoare[i]);
    }

    for (int i = 0; i <= capacitate; ++i)
        dp[i] = 0;

    int valoare_maxima = 0;

    for (int i = 1; i <= nr_obiecte; ++i) {
        for (int j = capacitate - greutate[i]; j >= 0; --j) {
            if (dp[j + greutate[i]] < dp[j] + valoare[i]) {
                dp[j + greutate[i]] = dp[j] + valoare[i];
                if (dp[j + greutate[i]] > valoare_maxima)
                    valoare_maxima = dp[j + greutate[i]];
            }
        }
    }

    fprintf(fout, "%d\n", valoare_maxima);

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