# include <bits/stdc++.h>
# pragma GCC optimize("O3")
# define maxn 500001
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define pb push_back
# define mp make_pair
//# define int ll
using namespace std;
const int inf = INT_MAX;

int dp[10001];
int n,G,w[5001],p[5001];
int ans;

int32_t main(){_
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    cin >> n >> G;
    for(int i = 1;i<=n;i++)
    {
        cin >> w[i] >> p[i];
    }
    for(int i = 1;i<=n;i++)
    {
		for(int j = G;j >= w[i];j--)
		{
			if(dp[j] < dp[j - w[i]] + p[i])
			{
				dp[j] = dp[j - w[i]] + p[i];
				ans = max(ans,dp[j]);
			}
		}
    }
	rc(ans);
}