#include <stdio.h>

#define MAX_N 5000

int maxProfit = 0;
int bestSubset[MAX_N];

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, int currentWeight, int currentProfit)
{
    if (currentWeight <= k && currentProfit > maxProfit)
    {
        maxProfit = currentProfit;
        for (int i = 0; i < n; i++)
        {
            bestSubset[i] = subset[i];
        }
    }

    if (index == n)
    {
        return;
    }

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

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

int main()
{
    int N, G;
    int W[MAX_N], P[MAX_N];
    int subset[MAX_N];

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

    fscanf(f, "%d %d", &N, &G);

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

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

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

    fclose(f);
    fclose(g);

    return 0;
}