#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <class F, class S>
bool chmax(F &u, const S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
long long int findMaxAttraction(int n, int s, int d, int attraction[]) {
vector <int> a(n);
for ( int i = 0; i < n; i++ ) a[i] = attraction[i];
i64 opt = 0, cnt = 0;
multiset <i64> A, B;
for ( int i = 0; i < min(n, d); i++ ){
B.insert(a[i]);
while ( !B.empty() && (int)A.size() < d - i ){
auto it = --B.end(); B.erase(it);
A.insert(*it); cnt += *it;
}
while ( (int)A.size() > d - i ){
auto it = A.begin(); A.erase(it);
B.insert(*it); cnt -= *it;
}
if ( !A.empty() && !B.empty() ){
while ( *A.begin() < *B.rbegin() ){
auto x = A.begin(); A.erase(x);
auto y = --B.end(); B.erase(y);
cnt += *y - *x;
A.insert(*y), B.insert(*x);
}
}
chmax(opt, cnt);
}
return opt;
}
