#include <fstream>
#include <vector>
#include <algorithm>

std::ifstream input ("rucsac.in");
std::ofstream output ("rucsac.out");

struct object {
    int weight;
    int profit;
};

int main () {

    int n, maxWeight;
    input >> n >> maxWeight;

    std::vector<object> objectArr(n);
    for (int i = 0; i < n; i++){
        input >> objectArr[i].weight >> objectArr[i].profit;
    }

    //dp[w] = max profit with w max weight
    int* dpPrevious = new int[maxWeight+1];
    int* dpCurrent = new int[maxWeight+1];
    for (int w = 0; w <= maxWeight; w++){
        dpPrevious[w] = 0;
    }

    //max profit calculation until the i-th object
    for (int i = 0; i < n; i++){
        for (int w = 0; w <= maxWeight; w++){
            //dpCurrent[w] = std::max(dpPrevious[w], (objectArr[i].profit + dpPrevious[w - objectArr[i].weight]));
            int wt = objectArr[i].weight;
            int pf = objectArr[i].profit;
            if (w >= wt) {
                dpCurrent[w] = std::max(dpPrevious[w], pf + dpPrevious[w - wt]);
            } else {
                dpCurrent[w] = dpPrevious[w];
            }
        }
        int* temp = dpPrevious;
        dpPrevious = dpCurrent;
        dpCurrent = temp;
    }

        // after the final swap the latest results live in dpPrevious
        output << dpPrevious[maxWeight];

    return 0;
}