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

typedef struct {
    int weight;
    int value;
} Item;

int max_value = 0;

Item* read_items(FILE *f, int count) {
    Item* items = malloc(count * sizeof(Item));
    if (!items) {
        printf("Memory allocation failed.\n");
        exit(1);
    }

    for (int i = 0; i < count; ++i) {
        fscanf(f, "%d %d", &items[i].weight, &items[i].value);
    }

    return items;
}

void backtrack(Item* items, int n, int index, int current_weight, int current_value, int max_weight) {
    if (index == n) {
        if (current_value > max_value)
            max_value = current_value;
        return;
    }

    backtrack(items, n, index + 1, current_weight, current_value, max_weight);

    if (current_weight + items[index].weight <= max_weight) {
        backtrack(items, n, index + 1,
                  current_weight + items[index].weight,
                  current_value + items[index].value,
                  max_weight);
    }
}

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

    if (!f || !o) {
        printf("Error opening file.\n");
        return 1;
    }

    int item_count, max_weight;
    fscanf(f, "%d %d", &item_count, &max_weight);

    Item* items = read_items(f, item_count);

    backtrack(items, item_count, 0, 0, 0, max_weight);

    fprintf(o, "%d\n", max_value);

    free(items);
    fclose(f);
    fclose(o);
    return 0;
}