#include <fstream>

using namespace std;

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


int d[3][10005];
int n, G;
int w[5005], p[5005];

int main()
{
    f>>n>>G;
    for(int i=1; i<=n; i++)
        f>>w[i]>>p[i];
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<w[i]; j++)
            d[i%2][j] = d[(i+1)%2][j];
        for(int j=w[i]; j<=G; j++)
        {
            d[i%2][j] = max(d[(i+1)%2][j-w[i]]+p[i], d[(i+1)%2][j]);
        }
    }
    g<<d[n%2][G];
    return 0;
}