#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> #include <tuple> #include <cmath> #include <numeric> #include <functional> #include <cassert> #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; const ll INF = 1e18; ll dp[3005][3005]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n, m; cin >> n >> m; vector<ll> a(n); for(int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end(), greater<ll>()); ll ans = 0; for(int i = 0; i < n; i++){ for(int j = 0; j <= m; j++){ // 何もしない chmax(dp[i+1][j], dp[i][j]); // a[i], a[i+1]を使う if(i+1 < n){ int d = a[i]-a[i+1]; if(j+d <= m) chmax(dp[i+2][j+d], dp[i][j]+a[i]); } } } for(int i = 0; i <= m; i++) chmax(ans, dp[n][i]); cout << ans << endl; }