#include <fstream>

using namespace std;

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

const int max_size = 5e3 + 1;

int dp[max_size], pr[max_size];

int main ()
{
    int n, g;
    in >> n >> g;
    dp[0] = 1;
    while (n--)
    {
        int x, w;
        in >> w >> x;
        for (int j = g; j - w >= 0; j--)
        {
            if (dp[j - w] == 1)
            {
                dp[j] = 1;
                pr[j] = max(pr[j - w] + x, pr[j]);
            }
        }
    }
    int mx = 0;
    for (int i = 1; i <= g; i++)
    {
        if (dp[i] == 1)
        {
            mx = max(mx, pr[i]);
        }
    }
    out << mx;
    in.close();
    out.close();
    return 0;
}