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

typedef struct 
{
    int value, weight;
}Prod;

float knapDiscret(Prod produse[], int N, float G)
{
    int rez = 0;
    int dp[10000] = {0};
    for(int i = 0 ; i < N ; i++)
    {
        for(int j = (G - produse[i].weight) ; j >= 0 ; j--)
        {
            if(dp[j + produse[i].weight] < dp[j] + produse[i].value)
            {
                dp[j + produse[i].weight] = dp[j] + produse[i].value;
                if(dp[j + produse[i].weight] > rez)
                {
                    rez = dp[j + produse[i].weight];
                }
            }
        }
    }
    return rez;
}
int main()
{
    int N;
    int G;
    Prod produse[5000];

    FILE *fin = fopen("rucsac.in", "r");
    FILE *fout = fopen("rucsac.out", "w");
    
    if(fin == NULL || fout == NULL) {
        printf("Eroare la deschiderea fisierelor!\n");
        return 1;
    }

    //printf("Introduceti numarul de obiecte si greutatea rucsacului:");
    fscanf(fin, "%d %d", &N, &G);
    
    for(int i = 0 ; i < N ; i++)
    {
        fscanf(fin, "%d %d", &produse[i].weight, &produse[i].value);
    }
    int max_value = knapDiscret(produse, N, G);
     
    fprintf(fout, "%d", max_value);
    fclose(fin);
    fclose(fout);
    return 0;
}