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

#define MAX_G 10001

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

int main(void)
{
    int N, G;
    int greutate[5001], profit[5001];
    int dp[MAX_G] = {0};

    FILE *fin = fopen("rucsac.in", "rt");
    FILE *fout = fopen("rucsac.out", "wt");

    if (fscanf(fin, "%d %d", &N, &G) != 2) {
        fprintf(stderr, "Eroare la citirea datelor\n");
        exit(1);
    }

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

    for (int i = 1; i <= N; i++) {
        for (int w = G; w >= greutate[i]; w--) {
            dp[w] = max(dp[w], dp[w - greutate[i]] + profit[i]);
        }
    }

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

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