#include <bits/stdc++.h>

using namespace std;

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

int n, c, G[5001], V[5001], L1[10001], L2[10001], sol;

void Read()
{
    fin >> n >> c;
    for (int i = 1; i <= n; ++i)
    {
        fin >> G[i] >> V[i];
    }
}

void Solve()
{
    for (int i = 0; i <= c; ++i)
    {
        L1[i] = 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = c; j - G[i] >= 0; --j)
        {
            L2[j] = L1[j];
            L2[j] = max(L2[j], V[i] + L1[j - G[i]]);
            sol = max(L2[j], sol);
        }
        for (int j = 0; j <= c; ++j)
        {
            L1[j] = L2[j];
        }
    }
    fout << sol;
}

int main()
{
    Read();
    Solve();
    fin.close();
    fout.close();
    return 0;
}