#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
struct elem{
int x, y;
bool operator < (const elem &aux)const{
if(x != aux.x) return x > aux.x;
return y < aux.y;
}
};struct elem2{
int x, y;
bool operator < (const elem2 &aux)const{
if(y != aux.y) return y < aux.y;
return x < aux.x;
}
};
elem a[200005];
elem2 b[200005];
int n;
int aib[200005];
map <int, int> f, f2;
void u(int x, int v){
for(int i = x; i <= n ; i = i + (i & (-i))) aib[i] += v;
}
int q(int x){
int ans = 0;
for(int i = x; i >= 1 ; i = i - (i & (-i))) ans += aib[i];
return ans;
}
int kth(int k){
int st = 1, dr = n;
while(st <= dr){
int mij = (st + dr) / 2;
if(q(n) - q(mij - 1) < k) dr = mij - 1;
else st = mij + 1;
}
return f2[dr];
}
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
int N = I.size();
n = N;
for(int i = 1; i <= N ; ++i){
a[i] = {I[i - 1], O[i - 1]};
b[i] = {I[i - 1], O[i - 1]};
}
sort(a + 1, a + N + 1);
sort(b + 1, b + N + 1);
for(int i = 1; i <= N ; ++i) f[b[i].y] = i, f2[i] = b[i].y;
for(int i = 1; i < K ; ++i) u(f[a[i].y], 1);
long long Sol = 0;
for(int i = K; i <= N ; ++i){
u(f[a[i].y], 1);
int X = a[i].x;
int Y = kth(K);
Sol = max(Sol, 2LL * X * Y - 1LL * X * X);
}
return Sol;
}
