// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

	scanf("%d%d", &n, &C);

	memset(f, -1, sizeof(f));

	f[0] = 0;

	for (int i = 1; i <= n; i++) {

		int w, v;

		scanf("%d%d", &w, &v);

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

			f[i] = max(f[i], f[i - w] + v);

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

	printf("%lld\n", ans);



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7567100394326827x):
#include <iostream>

#include <algorithm>

#include <map>

#include <set>

#include <vector>

#include <list>

#include <queue>

#include <sstream>

#include <cmath>

#include <functional>

using namespace std;



#define rep(i,n) for(int i=0;i<n;i++)

#define reps(s,i,n) for(int i=s;i<n;i++)

#define rev(i,n) for(int i=n-1;i>=0;i--)

#define skip(i,n,p) for(int i=0;i<n;i+=p)

#define all(a)  (a).begin(),(a).end()

#define int64 long long

#define debug cerr << __FILE__ << ":" << __LINE__ << endl;

#define INF 2147483647



struct Init {

    Init() {

        cin.tie(0);

        ios::sync_with_stdio(false);

        cout.precision(20);

        cout << fixed;

    }

} init;



template <typename _Ty>

ostream& operator << (ostream& ostr, const vector<_Ty>& v) {

    for(int i = 0; i < (int) v.size(); i++) {

        ostr << v[i] << (i + 1 != v.size() ? " " : "");

    }

    return ostr;

}



template <typename _K, typename _V>

ostream& operator << (ostream& ostr, const map<_K, _V>& v) {

    ostr << "{";

    for (auto iter = v.begin(); iter != v.end(); ++iter) {

        ostr << (*iter).first << ": " << (*iter).second << ", ";

    }

    ostr << "}";

    return ostr;

}



template <typename _K>

ostream& operator << (ostream& ostr, const set<_K>& v) {

    for (auto iter = v.begin(); iter != v.end(); ++iter) {

        ostr << *iter << (iter != v.end() ? " " : "");

    }

    return ostr;

}



template <typename _K, typename _V>

ostream& operator << (ostream& ostr, const pair<_K, _V>& v) {

    ostr << v.first << " " << v.second;

    return ostr;

}



int nCr(int n, int r) {

    int result = 1;

    rep(i, r) {

        result *= (n - i);

    }

    rep(i, r) {

        result = result / (i + 1);

    }



    return result;

}



int main() {

    int N, W; cin >> N >> W;

    vector<int> w(N), v(N); rep(i, N) cin >> w[i] >> v[i];



    vector<vector<int64>> dp(N+1, vector<int64>(W+1, 0));

    rep(i, N) {

        dp[i+1] = dp[i];

        rep(j, W) {

            if (w[i] + j <= W) {

                dp[i+1][w[i]+j] = max(dp[i+1][w[i]+j], dp[i][j] + v[i]);

            } else {

                dp[i+1][j] = max(dp[i+1][j], dp[i][j]);

            }

        }

    }



    cout << dp[N][W] << endl;

}