#include <iostream>

#define NMAX 5000
#define WMAX 10000

int main()
{
    int n;
    int w[NMAX]; // weight
    int v[NMAX]; // value
    int max_weight;
    int p[WMAX + 1];

    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    std::cin >> n >> max_weight;

    for (int i = 0; i < n; ++i)
        std::cin >> w[i] >> v[i];

    for (int weight = 1; weight <= max_weight; ++weight)
        p[weight] = 0;

    for (int i = 0; i < n; ++i)
        for (int weight = max_weight - w[i]; weight >= 0; --weight)
            p[weight + w[i]] = p[weight] + v[i] > p[weight + w[i]] ? p[weight] + v[i] : p[weight + w[i]];

    std::cout << p[max_weight] << '\n';

    return 0;
}