#include "cross.h"
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
multiset<long long> S; // keep as size K
vector<pair<int,int>> cross;
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
int N = I.size();
for(int i=0;i<N;++i){
cross.push_back({I[i],O[i]});
}
sort(cross.begin(),cross.end(),[](auto x,auto y){return x.first>y.first;});
long long mx=0;
for(int i=0;i<N;++i){
long long mi = cross[i].first;
// put the O in the set
S.insert(cross[i].second);
// keep the size(evict the smallest o)
if((int)S.size()>K) S.erase(S.begin());
if((int)S.size()<K) continue;
// get the smallest element
long long statQuo = (int)(*S.begin());
// update maxma
if(mx < 2 * statQuo * mi - mi * mi){
mx = 2 * statQuo * mi - mi * mi;
}
}
return mx;
}
