#pragma GCC optimize("O3", "unroll-loops", "fast-math", "no-stack-protector") #pragma GCC target("avx", "avx2") #pragma GCC option("arch=native") #include <bits/stdc++.h> using namespace std; #define ll long long #define vll vector<ll> #define len(x) (ll)x.size() const ll inf = 1e9, infl = 1e18; const ll MOD = 1e9 + 7; const ll maxn = 2e5 + 5; ll n, m, k = 0; void _() { // r = n subtasklari // Observation: eger range icinden cixaracagin ve range icine getireceyin indexleri secsen bes edir // cunki cost onlarin yerini nece deyissen de eyni qalir (eger rangeden eyni terefdedise) // n <= 13 subtaski ucun onda sadece range icinden max k dene element secsek colden optimal olan k dene // elementi secmek ucun bitmask ata bilerik cunki en pis halda n / 2 dene element secmeliyik range colunden. // Cunki, (k <= min(length of range, n - length of range)) max qiymeti ucun length of range = n / 2, // O(2^12) = O(4096), o da rahatliqla kecir. ll l, r, cm = 0, sz = 0, sz_ = 0; cin >> n >> l >> r >> m; // vector<array<ll, 2>> v, v_; array<ll, 2>v[30], v_[30]; for(ll i = 1, x; i <= n; i ++){ cin >> x; if(l <= i and i <= r){ v[sz ++] = {x, i}; cm += x; } else{ v_[sz_ ++] = {x, i}; } } ll cv = cm; for(ll msk = 0; msk < (1ll << sz); msk ++) for(ll msk_ = 0; msk_ < (1ll << sz_); msk_ ++){ if(__builtin_popcount(msk) != __builtin_popcount(msk_)) continue; ll i = 0, i_ = 0, cost = 0, sum = cm; while(i < sz and i_ < sz_){ while(i < sz and !(msk & (1ll << i))) i ++; while(i_ < sz_ and !(msk_ & (1ll << i_))) i_ ++; if(i < sz and i_ < sz_){ sum += - v[i][0] + v_[i_][0]; cost += abs(v[i][1] - v_[i_][1]); i ++, i_ ++; } if(cost > m) break; } if(cost <= m) cv = min(cv, sum); } cout << cv << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(0); ll t = 1; // cin >> t; while(t --) _(); }