#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[1000] = {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[100];

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