#include <stdio.h>
#include <stdlib.h>
//https://infoarena.ro/problema/rucsac
int max(int a, int b) {
    if (a>b) return a;
    return b;
}

int backtr(int i, int currentWeight, int currentProfit,int N, int G, int weight[], int profit[], int *maxProfit)
{
    if (currentWeight>G) return 0;

    if (i==N) {
        if (currentProfit>*maxProfit) {
            *maxProfit =currentProfit;
        }
        return 0;
    }
    //take it
    backtr(i+1, currentWeight + weight[i], currentProfit + profit[i],N, G, weight, profit, maxProfit);

    //or dont take it
    backtr(i+1, currentWeight, currentProfit,N, G, weight, profit, maxProfit);

    return *maxProfit;
}

int knapsackBacktr(int N, int G, int weight[], int profit[]) {
    int maxProfit =0;
    return backtr(0, 0, 0, N, G, weight, profit, &maxProfit);
}

int main() {
    FILE *fin=fopen("rucsac.in", "r");
    FILE *fout=fopen("rucsac.out", "w");

    if (fin==NULL || fout==NULL) {
        printf("Error opening the file\n");
        return 1;
    }
    int n, g;
    fscanf(fin, "%d %d", &n, &g);

    int *weight=(int *)malloc(n * sizeof(int));
    int *profit=(int *)malloc(n* sizeof(int));

    if (weight==NULL || profit==NULL) {
        printf("Error allocating memory\n");
        return 1;
    }

    for (int i=0; i<n; i++) {
        fscanf(fin, "%d %d", &weight[i], &profit[i]);
    }

    int solution=knapsackBacktr(n,g, weight, profit);
    fprintf(fout, "%d\n", solution);

    free(weight);
    free(profit);
    fclose(fin);
    fclose(fout);
    return 0;
}