#include <fstream>

using namespace std;

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

int maxp[5001][10001], i, j, n, G, nr=-1;

struct ura{
    int p,g;
}v[5001];

int dp (int k, int g)
{
    if(k==n) return 0;
    if(maxp[k][g]==-1)
    {
        maxp[k][g]=dp(k+1,g);
        if(g+v[k].g<=G)
            maxp[k][g]=max(maxp[k][g], dp(k+1, g+v[k].g)+v[k].p);
    }
    return maxp[k][g];
}

int main() {
    cin>>n>>G;
    for(i=0;i<n;i++)
        cin>>v[i].g>>v[i].p;
    for(i=0;i<=n;i++)
    for(j=0;j<=10000;j++)
            maxp[i][j]=-1;
        cout<<dp(0,0);
    return 0;
}