#include <bits/stdc++.h>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
int n, gr, i, j, mx, dp[5005][10005], x[5005], y[5005];
int main()
{
    ios_base::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
    in >> n >> gr;
    for (i = 1; i <= n; ++i)
        in >> y[i] >> x[i];
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= gr; ++j)
        {
            dp[1][j] = dp[0][j];
            if (j >= y[i])
                dp[1][j] = max (dp[0][j], dp[0][j - y[i]] + x[i]);
            if (i == n)
                mx = max (mx, dp[1][j]);
        }
        for (j = 1; j <= gr; ++j)
            dp[0][j] = dp[1][j];
    }
    out << mx;
}