#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("ruscac.out");
int n, G;
int W[5005];
int P[5005];
int Optim[5005];
int sol;

void Read()
{
    f>>n>>G;
    for(int i = 1;i <= n;++i)
        f>>W[i]>>P[i];
    f.close();
}

void Solve()
{
    for(int i = 1;i <= n;++i)
        for(int j = G - W[i];j >= 0;--j)
            if(Optim[j + W[i]] < Optim[j] + P[i])
            {
                Optim[j + W[i]] = Optim[j] + P[i];
                sol = max(sol, Optim[j + W[i]]);
            }
}

int main()
{
    Read();
    Solve();
    g<<sol;
    g.close();
    return 0;
}