#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define maprep(itr,M) for(auto itr=(M).begin(); itr!=(M).end(); ++itr)
#define mod (ll)(1e9+7)
#define inf (ll)(1e9+7)
#define d(x) cerr<<#x<<"="<<x<<endl;
#define p(x) cout<<(x)<<endl
#define ps(x) cout<<(x)
#define pk(x) cout<<(x)<<" "
#define pfix(d,x) cout << fixed << setprecision(d) << x << endl
#define parr(v) rep(i,sz(v)){pk(v[i]);}p("");
#define pmat(v,n,m) rep(i,n){rep(j,m){pk(v[i][j]);}p("");}
#define pb push_back
#define sz(v) (v).size()
#define all(v) (v).begin(), (v).end()
#define minel(v) *min_element(all(v))
#define minind(v) distance((v).begin(), min_element(all(v)))
#define maxel(v) *max_element(all(v))
#define maxind(v) distance((v).begin(), max_element(all(v)))
#define fi first
#define se second
#define pyn(x) {print_yes_no(x);return 0;}

template<class T> inline bool cm(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool ci(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

typedef map<ll, ll> imap;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<pair<ll,ll> > VP;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

void print_yes_no(bool ans){
    p(ans?"Yes":"No");
}

 
//Prime
bool is_prime(ll n){
	if(n==1)return false;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0)return false;
	}
	return true;
}


vector<ll>divisor(ll n){
	vector<ll>res;
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			res.push_back(i);
			if(i!=n/i)res.push_back(n/i);
		}
	}
	return res;
}
map<ll,int>prime_factor(ll n){
	map<ll,int>res;
	for(ll i=2;i*i<=n;i++){
		while(n%i==0){
			res[i]++;
			n/=i;
		}
	}
	if(n!=1)res[n]++;
	return res;
}
vector<ll>prime_enum(int n){
	vector<bool>is_prime(n+1,true);
	is_prime[0]=is_prime[1]=false;
	vector<ll>res;
	for(int i=2;i<=n;i++){
		if(!is_prime[i])continue;
		res.push_back(i);
		for(int j=2*i;j<=n;j+=i){
			is_prime[j]=false;
		}
	}
	return res;
}

//Mod
// mod_tools


#define MFACT_SIZE 1000001

ll fact[MFACT_SIZE]; 

ll mpow(ll x, ll y){
    //d(x)
    if(y==0) return 1;
    if(y%2==0){
        return mpow(x*x%mod,y/2)%mod;
    }
    else{
        return x*mpow(x,y-1)%mod;
    }
}

ll minv(ll x){
    // only available for mod=10^9+7
    return mpow(x,mod-2);
}

ll ms(ll a,ll b){
    return (a+b)%mod;
}

ll mm(ll a,ll b){
    return (a*b)%mod;
}

void mfact(){
    //prepare fact-array
    fact[0]=1;
    rep(i,1,MFACT_SIZE){
        fact[i]=fact[i-1]*i%mod;
    }
}

ll mcombi(ll n, ll k){
    return (fact[n]*minv(fact[k])%mod)*minv(fact[n-k])%mod;
}


ll llceil(ll a, ll b){
    if(a >= 0){
        return (a+b-1)/b;
    }else{
        return a/b;
    }
}
ll llfloor(ll a, ll b){
    if(a < 0){
        return (a-b+1)/b;
    }else{
        return a/b;
    }
}


struct UnionFind {
  VL data;
  UnionFind(int size) : data(size, -1) { }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool find(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  ll size(int x) {
    return -data[root(x)];
  }
  ll num_root(ll size){
    VL roots;
    rep(i,size)roots.pb(root(i));
    sort(all(roots));
    roots.erase(unique(all(roots)),roots.end());
    return roots.size();
  }
};


struct graph{
    ll V;
    vector<VP > v;
    graph(ll V) : V(V), v(vector<VP >(V)){}
    void add_diedge(ll v1, ll v2, ll w){
        v[v1].pb({v2, w});
        v[v2].pb({v1, w});
    }
    void add_edge(ll v1, ll v2, ll w){
        v[v1].pb({v2, w});
    }
    VL vval = vector<ll>(V, 0);
    VL dist = vector<ll>(V, -1);
    VL prever = vector<ll>(V,-1);
    set<ll> leaves;
    VL dijkstra(ll start){
        priority_queue<P, vector<P>, greater<P> > que;
        que.push(P(0,start));
        while(!que.empty()){
            P pa = que.top();
            que.pop();
            ll u = pa.se;
            if(dist[u] >= 0 && dist[u] < pa.fi)continue;
            dist[u]=pa.fi;
            for(P e : v[u]){
                if(dist[e.fi] < 0 || dist[e.fi] > dist[u] + e.se){
                    dist[e.fi] = dist[u] + e.se;
                    prever[e.fi] = u;
                    que.push(P(dist[e.fi],e.fi));
                }
            }
        }
        return dist;
    }
    void dfs(ll now, ll prv, ll c){
        vval[now]+=c;
        for(auto nxt : v[now])if(nxt.fi != prv){
            dfs(nxt.fi, now, vval[now]);
        }
    }
    VL bfs(ll start){
        VL dist(V,-1);
        queue<ll> Q;
        Q.push(start);
        dist[start]=0;
        ll now;
        while(!Q.empty()){
            now = Q.front();
            Q.pop();
            ll cnt=0;
            for(auto nxt : v[now]){
                if(dist[nxt.fi]==-1){
                    cnt++;
                    dist[nxt.fi]=0;
                    dist[nxt.fi]+=dist[now]+1;
                    Q.push(nxt.fi);
                }
            }
            if(cnt==0)leaves.insert(now);
        }
        return dist;
    }
    void gpr(){
        rep(i,V){ps(i);ps(": ");for(P x : v[i]){ps(x.fi);ps(",");ps(x.se);ps(" ");}p("");}
    }
    vector<VL> warshall_floyd() {
        vector<VL> dd = vector<VL>(V, VL(V,inf)); 
        rep(i,V)for(P e: v[i])dd[i][e.fi]=e.se;
        rep(k,V)rep(i,V)rep(j,V)dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j]);
        return dd;
    }
};


string st;

map<char,ll> marge_map(map<char,ll> s1,map<char,ll> s2){
    maprep(itr,s1){
        s2[itr->first]+=itr->second;
    }
    return s2;
}

struct SegmentTree {
private:
    int n;
    //vector<map<char,ll> > node;

public:
    vector<map<char,ll> > node;
    // 元配列 v をセグメント木で表現する
    SegmentTree(string v) {
    // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
    // セグメント木全体で必要なノード数は 2n-1 個である
    int sz = v.size();
    n = 1; while(n < sz) n *= 2;
    node.resize(2*n-1);
    for(int i=0; i<sz; i++) node[i+n-1][st[i]]++;
    for(int i=n-2; i>=0; i--) node[i] = marge_map(node[2*i+1], node[2*i+2]);
    }
    void update(int x,char b) {
    x += (n-1);
    node[x][st[x-(n-1)-1]]--;
    d(x-(n-1))
    st[x-(n-1)-1]=b;
    d(st)
    node[x][b]++;
    while(x > 0) {
        x = (x - 1) / 2;
        node[x] = marge_map(node[2*x+1], node[2*x+2]);
        }
    }
    // 要求区間 [a, b) 中の要素の最小値を答える
    // // k := 自分がいるノードのインデックス
    // // 対象区間は [l, r) にあたる
    // get a,b+1で呼び出す
    map<char,ll> get(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        d(l)d(r)d(a)d(b)
        map<char,ll> emp;
        if(r <= a || b <= l) return emp;
        // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
        if(a <= l && r <= b) return node[k];
        // 要求区間が対象区間の一部を被覆 -> 子について探索を行う
        // 左側の子を vl ・ 右側の子を vr としている
        // 新しい対象区間は、現在の対象区間を半分に割ったもの
        auto v1 = get(a, b, 2*k+1, l, (l+r)/2);
        auto v2 = get(a, b, 2*k+2, (l+r)/2, r);
        return marge_map(v1, v2);
    }    
};

ll a[1000001],b[100001],c[100001],d,n,m,x,y,z,h,w,k,mi=inf,ma=-inf,ans,sum,cnt,s,t,l,r,res,tmp,itr,q;
bool flag;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dx8[8]={1,1,0,-1,-1,-1,0,1},dy8[8]={0,1,1,1,0,-1,-1,-1};
char cha;
P pa;
bool fl;

ll dp[100001];

int main(void){
    ll n,W;
    cin>>n>>W;
    rep(i,n)cin>>a[i]>>b[i];
    rep(i,n)for(w=W;w>=0;w--)if(w+a[i]<=W)cm(dp[w+a[i]],dp[w]+b[i]);
    p(dp[W]);
    return 0;
}



Measured memory_bytes: 5120