#include <iostream>
#include <fstream>
#define maxN 5001

int max(int a, int b)
{
    if(a > b) return a;
    return b;
}

using namespace std;

int n, G, M[2 * maxN][maxN];
int W[maxN], V[maxN];

int KS(int g, int p)
{
    //cout << g << " " << p << endl;
    if(p > n)
        return 0;
    if(g < W[p])
    {
        if(M[g][p + 1] == -1)
            M[g][p + 1] = KS(g, p + 1);

        return M[g][p + 1];
    }
    if(M[g][p + 1] == -1)
        M[g][p + 1] = KS(g, p + 1);
    if(M[g - W[p]][p + 1] == -1)
        M[g - W[p]][p + 1] = KS(g - W[p], p + 1);

    return max(M[g][p + 1], V[p] + M[g - W[p]][p + 1]);
}

int main()
{


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

    f  >> n >> G;

    for(int i = 1; i <= n; i ++)
        f >> W[i] >> V[i];

    for(int i = 1; i <= G; i ++)
        for(int j = 1; j <= n; j ++)
        M[i][j] = -1;

    g << KS(G, 1);

    return 0;
}