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

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

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

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

    return items;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(Item* items, int item_count, int max_weight) {
    int* dp = calloc(max_weight + 1, sizeof(int));

    for (int i = 0; i < item_count; ++i) {
        for (int w = max_weight; w >= items[i].weight; --w) {
            dp[w] = max(dp[w], items[i].value + dp[w - items[i].weight]);
        }
    }

    int result = dp[max_weight];
    free(dp);
    return result;
}

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

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

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

    Item* items = read_items(f, item_count);

    int result = knapsack(items, item_count, max_weight);

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

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