#include <stdio.h>
#include <malloc.h>

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

int lengthOfArrays, *weightsArray = NULL, *profitsArray = NULL, knapCapacity, maxProfit, *maxSolutions = NULL;


int main () {
    FILE *inputFile, *outputFile;
    inputFile = fopen("input.txt", "r");
    outputFile = fopen("rucsac.out", "w");

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

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

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

    for(int index = 0; index < lengthOfArrays; ++index) {
        for(int jindex = knapCapacity; jindex >= weightsArray[index]; --jindex) {
            maxSolutions[jindex] = maxElem(maxSolutions[jindex], maxSolutions[jindex - weightsArray[index]] + profitsArray[index]);
            maxProfit = maxElem(maxProfit, maxSolutions[jindex]);
        }
    }

    printf("%d\n", maxProfit);
    return 0;
}