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

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

int knapSackBK(int knapCapacity, const int weightsArray[], int profitArray[], int lengthArray) {

    if (lengthArray == 0 || knapCapacity == 0)
        return 0;

    if (weightsArray[lengthArray - 1] > knapCapacity) {
        return knapSackBK(knapCapacity, weightsArray, profitArray, lengthArray - 1);
    } else {
        return maxElem(profitArray[lengthArray - 1] + knapSackBK(knapCapacity - weightsArray[lengthArray - 1], weightsArray, profitArray, lengthArray - 1),
                       knapSackBK(knapCapacity, weightsArray, profitArray, lengthArray - 1));
    }
}

// Driver code
int main() {
    FILE *inputFile, *outputFile;
    inputFile = fopen("rucsac.in", "r");
    outputFile = fopen("rucsac.out", "w");
    int lengthOfArrays, *weightsArray = NULL, *profitsArray = NULL, knapCapacity;

    fscanf(inputFile, "%d", &lengthOfArrays);
    fscanf(inputFile, "%d", &knapCapacity);

    profitsArray = (int *) malloc((lengthOfArrays) * sizeof(int));
    weightsArray = (int *) malloc((lengthOfArrays) * sizeof(int));

    for (int index = 0; index < lengthOfArrays; ++index) {
        fscanf(inputFile, "%d", &weightsArray[index]);
        fscanf(inputFile, "%d", &profitsArray[index]);

    }

    fclose(inputFile);

    fprintf(outputFile ,"%d\n", knapSackBK(knapCapacity, weightsArray, profitsArray, lengthOfArrays));

    free(profitsArray);
    free(weightsArray);
    fclose(outputFile);

    return 0;
}