#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll sq(int x) {
return (ll) x * x;
}
ll plotas(int r, int R) {
return sq(R) - sq(R-r);
}
ll SelectCross(int k, std::vector<int> r, std::vector<int> R) {
int n = r.size();
ll ans = 0;
//for(int i = 0; i < n; i++) {
//ans = max(ans, plotas(r[i], R[i]));
//}
vector<pair<int, int>> a(n);
for(int i = 0; i < n; i++) {
a[i] = {R[i], r[i]};
}
multiset<int> st;
auto rem = [&](int x) {
st.erase(st.find(x));
};
sort(a.rbegin(), a.rend());
for(int i = 0; i < n; i++) {
if ((int) st.size() < k) {
st.insert(a[i].second);
}
else {
if (*st.begin() < a[i].second) {
rem(*st.begin());
st.insert(a[i].second);
}
}
if ((int) st.size() == k) {
ans = max(ans, plotas(*st.begin(), a[i].first));
//cout << a[i].first << " " << *st.begin() << " " << plotas(*st.begin(), a[i].first) << "\n";
}
}
return ans;
}
