#include <stdio.h>
#include <stdlib.h>
FILE *fin = NULL;
FILE *fout = NULL;
#define MAX_SIZE_STACK 100
int profitmax = 0;
int greutatemax = 0;
int nrsol = 0;
typedef struct
{
    int g;
    int p;
    float pg;
} rucsac;
FILE *openfile(char *filename, char *type)
{
    FILE *fin = NULL;
    if ((fin = fopen(filename, type)) == NULL)
    {
        printf("fisierul nu a putut sa fie deschis");
        exit(EXIT_FAILURE);
    }
    return fin;
}
void citireR(rucsac *v, int N)
{
    for (int i = 0; i < N; i++)
    {
        fscanf(fin, "%d %d", &v[i].g, &v[i].p);
        v[i].pg = (float)v[i].p / v[i].g;
    }
}
void afisareR(rucsac *v, int N)
{
    fprintf(fout, "\n");
    for (int i = 0; i < N; i++)
    {
        fprintf(fout, "%d %d %.02f\n", v[i].g, v[i].p, v[i].pg);
    }
    fprintf(fout, "\n");
}
void push(int *st, int item, int *top)
{
    if ((*top) == (MAX_SIZE_STACK - 1))
    {
        printf("stiva este plina\n");
        return;
    }
    st[++(*top)] = item;
}

int pop(int *st, int *top)
{
    if ((*top) == -1)
    {
        printf("stiva este goala");
        return -1;
    }
    return st[(*top)--];
}
void displayitems(int *st, int top, int m, rucsac *R, int G)
{
    int gsol = 0;
    int profitsol = 0;
    if (top == -1)
    {
        printf("stiva este goala");
        return;
    }

    for (int i = 0; i <= top; i++)
    {
        gsol += R[st[i]].g;
        profitsol += R[st[i]].p;
        //printf("%d ", R[st[i]].g);
    }
    if (gsol <= G)
    {
        if (profitmax < profitsol)
        {
            greutatemax = gsol;
            profitmax = profitsol;
            nrsol = m;
        }
    }
   // printf("\n");
}
void backtracking(rucsac *A, int *subset, int indx, int n, int top, int k, int *m, int G)
{
    if (top == k - 1)
    {
        //printf("%d: ", ++(*m));
        displayitems(subset, top, *m, A, G);
    }
    for (int i = indx; i < n; i++)
    {
        push(subset, i, &top);
        backtracking(A, subset, i + 1, n, top, k, m, G);
        pop(subset, &top);
    }
    return;
}
int main()
{
    int v[100];
    int N, G;
    int m = 0;

    fin = openfile("data_in.txt", "r");
    fout = openfile("data_out.txt", "w");
    fscanf(fin, "%d %d", &N, &G);
    rucsac R[15];
    citireR(R, N);
    //afisareR(R, N);
    for (int i = 1; i <= N; i++)
    {
        backtracking(R, v, 0, N, -1, i, &m, G);
    }
    fprintf(fout, "%d", profitmax);
    return 0;
}