#include <iostream>
#include <fstream>
using namespace std;

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

int n,g;
int d[5001][5001];
int w[5001],p[5001];

int rucsac(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]=rucsac(i-1,j);
    return d[i][j]=max(rucsac(i-1,j),rucsac(i-1,j-w[i])+p[i]);
}

int main(){
    fin>>n>>g;
    for(int i=1;i<=n;++i){
        fin>>w[i]>>p[i];
    }
    fout << rucsac(n,g);
    fin.close();
    fout.close();
    return 0;
}