#include <fstream>

using namespace std;
using PII = pair<int, int>;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

constexpr int NMAX = (int)(5e3 + 1);
constexpr int WMAX = (int)(1e4 + 1);
const int INF = (int)(1e9);

int N, W;
PII v[NMAX];

int dp[WMAX];

static inline void read()
{
    f.tie(nullptr);

    f >> N >> W;

    for (int i = 1; i <= N; ++i)
        f >> v[i].first >> v[i].second;

    return;
}

static inline int my_max(const int &a, const int &b)
{
    return ((a > b) ? a : b);
}

int main()
{
    read();

    dp[0] = 0;
    for (int i = 1; i <= W; ++i)
        dp[i] = -INF;

    for (int i = 1; i <= N; ++i)
    {
        int weight = v[i].first, profit = v[i].second;

        for (int j = (W - weight); j >= 0; --j)
            if (dp[j] != (-INF))
                dp[j + weight] = my_max(dp[j + weight], dp[j] + profit);
    }

    int ans = 0;
    for (int i = W; i >= 1; --i)
        ans = my_max(ans, dp[i]);

    g << ans << '\n';

    return 0;
}