#include "cross.h"
#include <queue>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
struct cross{
int d0;
int d1;
};
struct cross C[200000];
bool comp0(struct cross a, struct cross b){
return a.d0>b.d0;
}
bool comp1(struct cross a, struct cross b){
return a.d1>b.d1;
}
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
vector<struct cross> C;
priority_queue<int, vector<int>, greater<int> > PQ;
struct cross temp;
int N = I.size();
for (int i=0; i<N; i++){
temp.d0 = I[i];
temp.d1 = O[i];
C.push_back(temp);
}
sort(C.begin(), C.end(), comp0);
int j=0;
long long int max = 0;
long long int dmin0 = 1000000000;
long long int dmin1;
for (int i=0; i<K; i++){
PQ.push(C[j].d1);
dmin0 = C[j].d0;
//printf("!%d %d\n", C[j].d1, C[j].d0);
j++;
}
long long int t;
while(true){
dmin1 = PQ.top();
t = -dmin0*dmin0 + 2*dmin0*dmin1;
//printf("!!%d\n",t);
if (t>max){
max = t;
}
if (j == N){
break;
}
while(dmin1>=C[j].d1 && j!=N){
j++;
}
if (j == N){
break;
}
PQ.pop();
PQ.push(C[j].d1);
dmin0 = C[j].d0;
j++;
}
return max;
}
