#include <fstream>
#define DIM 5005
#define INF 10012
using namespace std;

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

int N,W[DIM],cost[2*DIM],G,P[DIM],maxim=-INF;
int main(){
    fin>>N>>G;
    for(int i=1;i<=N;i++)
        fin>>W[i]>>P[i];
    for(int i=1;i<=G;i++)
        cost[i]=-INF;
    for(int i=1;i<=N;i++){
        for(int j=G;j>=0;j--)
            if(cost[j]!=-INF)
                if(j+W[i]<=G){
                    cost[j+W[i]]=max(cost[j+W[i]],cost[j]+P[i]);
                    maxim=max(cost[j+W[i]],maxim);
                }
    }
    fout<<maxim;
    fin.close();fout.close();
    return 0;
}