#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N, G;
int W[10005], P[10005], OP[10005], sol;
void read()
{
    fin >> N >> G;
    for(int i = 1; i <= N; i++)
        fin >> W[i] >> P[i];
}

void solve()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = G - W[i]; j >= 0; j--)
        {
            if(OP[j + W[i]] < OP[j] + P[i])
            {
                OP[j + W[i]] = OP[j] + P[i];
                if(OP[j + W[i]] > sol)
                    sol = OP[j + W[i]];
            }
        }
    }
}

int main()
{
    read();
    solve();
    fout << sol;
    return 0;
}