//author - noobiesAG

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b)         for(i=a;i<b;i++)
#define repd(i,a,b)        for(i=a;i>b;i--)
#define int                long long
#define pb                 push_back
#define mp                 make_pair
#define ld                 long double
#define vi                 vector<int>
#define vvi                vector<vector<int>>
#define pii                pair<int,int>
#define mii                map<int,int>
#define umap               unordered_map
#define all(c)             c.begin(),c.end()
#define si(c)              (int)c.size()
#define lb                 lower_bound
#define ub                 upper_bound
#define gi                 greater<int>
#define rev                reverse
#define ff                 first
#define ss                 second
#define yes                cout << "YES" << endl
#define no                 cout << "NO" << endl
#define ayes               cout << "Yes" << endl;
#define ano                cout << "No" << endl;
#define imp                cout << "IMPOSSIBLE" << endl
#define nl                 cout << endl
#define hello              cout << "hello" << endl
#define sp(x)              fixed << setprecision(x)
#define re                 return
#define p_q                priority_queue
#define FAST               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

//debugging
void dbg_out(){cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

const double pi = 3.14159265359;
const int mod = 1000000007;
const int modc = 998244353;
const int inf = LLONG_MAX;
const int neg_inf = LLONG_MIN;

int inline power(int a, int b, int p){
    a %= p;
    int ans = 1;
    while(b>0){
        if(b & 1)
            ans = (ans*a)%p;
        a = (a*a)%p;
        b >>= 1;
    }
    return ans;
}

int mod_inv(int n, int p){
    return power(n,p-2, p);
}

bool inline isPrime(int n) {
    if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
    return true;
}
template<typename... T>
void W(T&&... args)
{
	((cout << sp(9) <<  args << " "), ...);
	nl;
}
template<typename... T>
void R(T&&... args)
{
	((cin >> args), ...);
}
int ston(string s) 
{
	int a = 0;
	reverse(s.begin(),s.end());
	int pow = 1;
	for(int i=0;i<s.size();i++)
	{
		a += pow*(s[i]-'0');
		pow*=10;
	}
	return a;
}
template <class T>
string to_binary(T n) 
{
	string binaryNum;
	int i = 0;
	while (n > 0) {
		binaryNum.pb((n % 2)+'0');
		n = n / 2;
		i++;
	}
	reverse(binaryNum.begin(),binaryNum.end());
	return binaryNum;
}
template<class T>
void wv(T &v)
{
	for(auto x : v)
		cout << x << " " ;
	nl;
}
template<class T>
void rv(T &v)
{
	for(int i=0;i<si(v);i++)
		cin >> v[i];
}

//to safe_guard unordered_map<> in STL
//now declare something as unordered_map<int,int,custom_hash>mp :)
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int M = 2e5;

void solve()
{
	int i,j,sum = 0,prod = 1,maxl = neg_inf, minl = inf;
	int n,W;
	cin >> n >> W;
	vi w(n),v(n);
	rep(i,0,n)
		cin >> w[i] >> v[i];
	int dp[n][W+1];
	for(i=0;i<n;i++)
		for(j=0;j<=W;j++)
			dp[i][j] = 0;
	dp[0][w[0]] = v[0];
	for(i=1;i<n;i++)
	{
		for(j=0;j<=W;j++)
		{
			dp[i][j] = dp[i-1][j];
		}
		for(j=0;j<=W;j++)
		{
			if(j + w[i] <= W)
			{
				dp[i][j+w[i]] = max(dp[i][j+w[i]],v[i]+dp[i-1][j]);
			}
		}
	}
	/*
	for(i=0;i<n;i++)
	{
		for(j=0;j<=W;j++)
			cout << dp[i][j] << ' ' ;
		nl;
	}
	*/
	for(i=0;i<=W;i++)
		maxl = max(maxl,dp[n-1][i]);
	cout << maxl << endl;
}
int32_t main()
{
	FAST;
	int t = 1;
	while(t--)
	{
		solve();
	}
} 


Measured memory_bytes: 81668