#include <fstream>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");
int daux[10002];
int d[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[j] = daux[j];
        }

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

        for(int j = 1; j<=g; j++)
        {
            daux[j] = d[j];
        }
    }

    out<<d[g];

    return 0;
}