#include <fstream>

#define MAXN 5012
#define MAXG 10012

using namespace std;

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

int n, g;
short int castig[MAXN][MAXG];
short 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)
            {
                if (castig[i - 1][j - gr[i] + p[i]] > castig[i - 1][j])
                    castig[i][j] = castig[i - 1][j - gr[i]] + p[i];
                else castig[i][j] = castig[i - 1][j];
            }
            else
                castig[i][j] = castig[i - 1][j];
        }
    }

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

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

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