#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

int GR[5001], P[5001], n;

int rez(int G, int k)
{
    if(k - 1 == n)
        return 0;

    if(G < GR[k])
        return rez(G, k + 1);
    else
        return max(rez(G, k + 1), P[k] + rez(G - GR[k], k + 1));
}

int main()
{

    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int gm;
    cin>>n>>gm;

    for(int i=1;i<=n;++i)
        cin>>GR[i]>>P[i];

    cout<<rez(gm, 1)<<"\n";
    return 0;
}