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

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


obiect v[5000];
int dp[10000] = {0};

int main(void)
{

    int n, G;

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

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

    fscanf(fin, "%d %d", &n, &G);

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

    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;
            }
        }
    }
    
    int Pmax = 0;
    for(int i = 0; i <= G; i++) {
        if(dp[i] > Pmax) {
            Pmax = dp[i];
        }
    }

    fprintf(fout, "%d\n", Pmax);
    fclose(fin);
    fclose(fout);
    return 0;
}