#include <iostream>
#include <fstream>
#define NMAX 5000
#define NMAX1 10000
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int D[NMAX][NMAX],n,g,w[NMAX1],p[NMAX1];
int rec(int i,int j)
{
    if(i==0) return 0;
    if(D[i][j]!=0) return D[i][j];
    if(j<w[i]) return D[i-1][j]=rec(i-1,j);
    return D[i][j]=max(rec(i-1,j),rec(i-1,j-w[i])+p[i]);
}
int main()
{
    in>>n>>g;
    for(int i=1; i<=n; i++)
        in>>w[i]>>p[i];
    out <<rec(n,g);
    return 0;
}