#include <fstream>

using namespace std;

const int MAXG = 10002;
const int MAXN = 5003;

int smax[MAXG];
int w[MAXN], p[MAXN];

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    int n, g;
    in >> n >> g;
    for (int i = 1; i <= n; i++)
        in >> w[i] >> p[i];

    for (int j = 1; j <= n; j++)
    {
        for (int i = g; i >= 0; i--)
        {
            if (w[j] + i <= g)
            {
                if (smax[w[j]+i] < smax[i] + p[j])
                    smax[w[j]+i] = smax[i] + p[j];
            }
        }
    }

    out << smax[g] << '\n';

    return 0;
}