#include "cross.h"
#include <algorithm>
#include <utility>
#include <set>
std::vector<std::pair<int, int> > p;
std::multiset<int> st;
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
int N = I.size();
for (int i = 0; i < N; i++)
p.push_back(std::make_pair(O[i], I[i]));
std::sort(p.begin(), p.end()); std::reverse(p.begin(), p.end());
for (int i = 0; i < K - 1; i++)
st.insert(p[i].second);
st.insert(2000000000);
auto si = st.begin();
long long ans = 0;
for (int i = K - 1; i < N; i++) {
int t = p[i].first - std::min((*si), p[i].second);
ans = std::max(ans, 1LL * p[i].first * p[i].first - 1LL * t * t);
if (p[i].second >(*si)) {
st.insert(p[i].second); ++si;
}
}
return ans;
}
