#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define ff first
#define ss second
vector<pii> A;
vector<int> xx;
int N;
const int SIZE = 1 << 18;
struct ST {
int A[SIZE << 1];
void update(int x, int v) {
for (x += SIZE; x; x >>= 1) A[x] += v;
}
int query(int v) {
int x = 1;
while (x < SIZE) {
if (A[x << 1 | 1] >= v) x = x << 1 | 1;
else {
x <<= 1;
v -= A[x | 1];
}
}
return x - SIZE;
}
} seg;
ll SelectCross(int K, std::vector<int> I, std::vector<int> O) {
N = I.size();
for (int i = 0; i < N; ++i) A.emplace_back(I[i], O[i]);
sort(A.rbegin(), A.rend());
for (auto i : A) xx.push_back(i.ss);
sort(xx.begin(), xx.end());
xx.erase(unique(xx.begin(), xx.end()), xx.end());
for (auto &i : A) i.ss = lower_bound(xx.begin(), xx.end(), i.ss) - xx.begin();
int cnt = 0;
long long ans = 0;
for (auto i : A) {
seg.update(i.ss, 1);
cnt++;
if (cnt < K) continue;
ans = max(ans, 2ll * i.ff * xx[seg.query(K)] - (ll) i.ff * i.ff);
}
return ans;
}
