#include <fstream>

#define MAXN 5000
#define MAXG 10002

using namespace std;

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

int n, g;
int castig[MAXN][MAXG];
int p[MAXN], gr[MAXN];

inline void Read()
{
    fin >> n >> g;

    for (int i = 1; i <= n; i++)
    {
        fin >> gr[i] >> p[i];
    }
}

inline void Solve()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= g; j++)
        {
            if (j - gr[i] >= 0)
            {
                castig[i][j] = max(castig[i - 1][j - gr[i]] + p[i], castig[i - 1][j]);
            }
        }
    }

    fout << castig[n][g];
}

int main ()
{
    Read();
    Solve();

    fin.close(); fout.close(); return 0;
}