#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "squad.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
const int MAXN = 300005;
struct pi{
int first, second, idx, cnt;
bool operator<(const pi &q)const{
return make_pair(first, second) < make_pair(q.first, q.second);
}
};
lint ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
struct convex_hull{
vector<pi> V;
void init(vector<pi> inp){
for(auto &i : inp){
while(sz(V) >= 2 && ccw(V[sz(V) - 2], V.back(), i) > 0) V.pop_back();
V.push_back(i);
}
}
pair<lint, int> get(int x, int y){
lint cur = -5e18;
int cnt = 0;
int pos = -1;
if(sz(V)){
int s = 0, e = sz(V) - 1;
while(s != e){
int m = (s+e)/2;
lint qr1 = 1ll * V[m].first * x + 1ll * V[m].second * y;
lint qr2 = 1ll * V[m+1].first * x + 1ll * V[m+1].second * y;
if(qr1 < qr2) s = m + 1;
else e = m;
}
for(int i=s; i<sz(V) && i<s+2; i++){
lint qr = 1ll * V[i].first * x + 1ll * V[i].second * y;
if(qr > cur){
cur = qr;
cnt = 0;
pos = V[i].idx;
}
if(qr == cur) cnt += V[i].cnt;
}
}
if(cnt >= 2) pos = -1;
return make_pair(cur, pos);
}
}X, Y, FUCKX[MAXN], FUCKY[MAXN];
int N;
vector<pi> v, w;
vector<pi> norm(vector<pi> v){
sort(v.begin(), v.end());
vector<pi> w;
for(int i=0; i<sz(v); ){
int e = i;
while(e < sz(v) && make_pair(v[i].first, v[i].second) == make_pair(v[e].first, v[e].second)) e++;
w.push_back({v[i].first, v[i].second, v[i].idx, e - i});
i = e;
}
return w;
}
int revX[MAXN], revY[MAXN];
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
N = sz(A);
for(int i=0; i<N; i++){
v.push_back({A[i], P[i], i, 1});
w.push_back({D[i], P[i], i, 1});
}
v = norm(v);
w = norm(w);
X.init(v);
Y.init(w);
for(int i=0; i<sz(v); i++) revX[v[i].idx] = i;
for(int i=0; i<sz(w); i++) revY[w[i].idx] = i;
for(int i=0; i<sz(X.V); i++){
int l = X.V[max(i - 1, 0)].idx;
int r = X.V[min(i + 1, sz(X.V) - 1)].idx;
l = revX[l];
r = revX[r];
vector<pi> fuck;
for(int j=l; j<=r; j++){
if(v[j].idx != X.V[i].idx) fuck.push_back(v[j]);
}
FUCKX[X.V[i].idx].init(fuck);
}
for(int i=0; i<sz(Y.V); i++){
int l = Y.V[max(i - 1, 0)].idx;
int r = Y.V[min(i + 1, sz(Y.V) - 1)].idx;
l = revY[l];
r = revY[r];
vector<pi> fuck;
for(int j=l; j<=r; j++){
if(w[j].idx != Y.V[i].idx) fuck.push_back(w[j]);
}
FUCKY[Y.V[i].idx].init(fuck);
}
}
long long BestSquad(int sex, int sey){
auto qr1 = X.get(sex, sey);
auto qr2 = Y.get(sex, sey);
if(qr1.second < 0 || qr2.second < 0 || qr1.second != qr2.second) return qr1.first + qr2.first;
lint ret = -5e18;
ret = max(ret, qr1.first + FUCKY[qr1.second].get(sex, sey).first);
ret = max(ret, qr2.first + FUCKX[qr2.second].get(sex, sey).first);
return ret;
}
