#include <stdio.h>

#define MAX_N 5000

int maxProfit = 0;  // variabila pentru a stoca profitul maxim
int bestSubset[MAX_N];  // Vector pentru a stoca subsetul optim

int calculateProfit(int *W, int *P, int *subset, int n)
{
    int totalProfit = 0;
    for (int i = 0; i < n; i++)
    {
        if (subset[i] == 1) 
        {
            totalProfit += P[i];
        }
    }
    return totalProfit;
}

void generateSubsets(int *W, int *P, int *subset, int n, int k, int index)
{
    if (index == n) 
    {
        int subsetWeight = 0;
        for (int i = 0; i < n; i++)
        {
            if (subset[i] == 1)
            {
                subsetWeight += W[i];
            }
        }
        if (subsetWeight <= k) 
        {
            int subsetProfit = calculateProfit(W, P, subset, n);
            if (subsetProfit > maxProfit) 
            {
                maxProfit = subsetProfit;
                for (int i = 0; i < n; i++) 
                {
                    bestSubset[i] = subset[i];
                }
            }
        }
    } 
    else 
    {
        subset[index] = 0;
        generateSubsets(W, P, subset, n, k, index + 1);

        subset[index] = 1;
        generateSubsets(W, P, subset, n, k, index + 1);
    }
}

int main() {
    int N, G;  // N- Numere    G - greutate max rucsac
    int W[MAX_N], P[MAX_N];  // greutate obeict i     valoare obiect i
    int subset[MAX_N];

    FILE *f, *g;

    f=fopen("rucsac.in","r");
    g=fopen("rucsac.out","w");

    fscanf(f,"%d %d",&N,&G);                       // N-numere    G-greutate max rucsac

    for (int i = 0; i < N; i++) 
    {
        fscanf(f,"%d %d", &W[i], &P[i]);              // greutate obiect i      valoare obiect i
    }

    generateSubsets(W, P, subset, N, G, 0);

    fprintf(g,"%d", maxProfit);

    fclose(f);
    fclose(g);

    return 0;
}