#include <fstream>
#define maxn 5001
#define maxg 10005
using namespace std;

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

int n, g;
int rucsac[2][maxg];

int w[maxn], p[maxn];

int main()
{
    fin >> n >> g;

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

    for(int i = 0; i <= n; ++i)
    {
        for(int j = 0; j <= g; ++j)
        {
            if(i == 0 || j == 0)
            {
                rucsac[i % 2][j] = 0;
            }
            else if(w[i] <= j)
            {
                rucsac[i % 2][j] = max(rucsac[(i - 1) % 2][j], rucsac[(i - 1) % 2][j - w[i]] + p[i]);
            }
            else rucsac[i % 2][j] = rucsac[(i - 1) % 2][j];
        }
    }

    fout << rucsac[n % 2][g];
    return 0;
}