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

double max(double a, double b)
{
    return (a > b) ? a : b;
}

int main(void)
{
    int N = 0, G = 0;
    double greutate[5001] = {0}, profit[5001] = {0};
    int a[2][5001] = {0};

    FILE *fin = fopen("rucsac.in", "rt");
    if (fin == NULL) {
        perror("eroare la deschiderea fisierului de intrare");
        exit(-1);
    }

    FILE *fout = fopen("rucsac.out", "wt");
    if (fout == NULL) {
        perror("eroare la deschiderea fisierului de iesire");
        exit(-1);
    }

    if (fscanf(fin, "%d %d", &N, &G) != 2) {
        perror("eroare la citirea N si G");
        exit(-1);
    }

    for (int i = 1; i <= N; i++)
        fscanf(fin, "%lf %lf", &greutate[i], &profit[i]);

    for (int i = 1; i <= N; i++) {
        for (int w = 0; w <= G; w++) {
            a[i % 2][w] = a[(i - 1) % 2][w];
            if (w >= (int)greutate[i])
                a[i % 2][w] = max(a[i % 2][w],a[(i - 1) % 2][w - (int)greutate[i]] + profit[i]);
        }
    }

    fprintf(fout, "%d\n", a[N % 2][G]);

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