#include <fstream>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");
int d[5002][10002];
int n, g;
int p[5002];
int w[5002];

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 = 1; j<w[i]; j++)
        {
            d[i][j] = d[i-1][j];
        }

        for(int j = w[i]; j<=g; j++)
        {
            d[i][j] = max(d[i-1][j], d[i-1][j-w[i]] + p[i]);
        }
    }

    out<<d[n][g];

    return 0;
}