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

#define max(A, B) ((A) > (B))?(A):(B)

typedef struct
{
    int g, p;
}data;

void read_data(FILE *in, data *d, int n)
{
    for(int i = 0; i < n; i++)
        fscanf(in, "%d %d", &d[i].g, &d[i].p);
}

void backtrack(data *d, int n, int g, int g_tot, int p_tot, int *prof_max, int *vizitat, int prev)
{
    if(g_tot > g)
    {
        *prof_max = max(p_tot-d[prev].p, *prof_max);
        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(vizitat[i])
            continue;

        p_tot += d[i].p;
        g_tot += d[i].g;
        vizitat[i] = 1;

        backtrack(d, n, g, g_tot, p_tot, prof_max, vizitat, i);

        p_tot -= d[i].p;
        g_tot -= d[i].g;
        vizitat[i] = 0;
    }
}

int solve(data *d, int g, int n)
{
    int *vizitat = NULL, prof_max = 0;

    if((vizitat = (int*)calloc(n, sizeof(int))) == NULL)
    {
        fprintf(stderr, "\nBad alloc\n");
        exit(EXIT_FAILURE);
    }

    backtrack(d, n, g, 0, 0, &prof_max, vizitat, 0);

    free(vizitat);
    return prof_max;
}

int main()
{
    FILE *in = NULL, *out = NULL;
    if((in = fopen("rucsac.in", "r")) == NULL || (out = fopen("rucsac.out", "w")) == NULL)
    {
        fprintf(stderr, "\nFile opening error\n");
        exit(EXIT_FAILURE);
    }

    int n, g;
    fscanf(in, "%d %d", &n, &g);
    data *d = (data*)malloc(sizeof(data)*n);
    read_data(in, d, n);

    fprintf(out, "%d\n", solve(d, g, n));

    free(d);
    fclose(in);
    fclose(out);
    return 0;
}