#include <fstream>
#define nMAX 5005
#define GMAX 10005

using namespace std;

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

int p[nMAX], w[nMAX], d[GMAX];

int n, g, maxim;

int main()
{
    in>>n>>g;
    for(int i=1; i<=n; i++)
        in>>w[i]>>p[i];
    for(int i=1; i<=n; i++)
    {
        for(int j=g; j>=w[i]; j--)
        {
            d[j] = max(d[j-w[i]]+p[i],d[j]);
        }
    }
    for(int i=0; i<=g; i++)
    {
        maxim = max(maxim, d[i]);
    }
    out<<maxim;
    return 0;
}