#include <fstream>
#include <algorithm>

using namespace std;

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

int n, k, l;
int p[5001], g[10001], d[2][10001];

int main()
{
    in >> n >> k;

    for (int i = 1; i <= n; i++)
        in >> g[i] >> p[i];

    for (int i = 1; i <= n; i++)
    {
        l = 1 - l;

        for (int j = 0; j <= k; j++)
        {
            d[1 - l][j] = d[l][j];

            if (j >= g[i])
            d[1 - l][j] = max(d[1 - l][j], d[1 - l][j - g[i]]+ p[i]);
        }
    }

    out << d[1 - l][k];

    return 0;
}