#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300010;
typedef long long lint;
struct DOT {
int x, y, idx;
DOT(int x = 0, int y = 0, int idx = 0) : x(x), y(y), idx(idx) {}
bool operator < (DOT a) const { return x != a.x ? x < a.x : y > a.y; }
};
int N;
vector<DOT> att[2], def[2];
bool bo[MAXN];
lint cp(DOT a, DOT b) { return lint(a.x) * b.y - lint(a.y) * b.x; }
lint ccw(DOT a, DOT b, DOT c) {
return cp(a, b) + cp(b, c) + cp(c, a);
}
void gch(int N, vector<DOT> &v, vector<DOT> &ch) {
if(!N) return;
int t = 0;
for(int i = 0; i < N; i++) if(v[i].y >= v[t].y) t = i;
ch.push_back(v[t]);
for(int i = t + 1; i < N; i++) {
while(ch.size() > 1 && ccw(ch[ch.size() - 2], ch.back(), v[i]) >= 0) ch.pop_back();
ch.push_back(v[i]);
}
for(auto a : ch) bo[a.idx] = true;
}
void gbest(int N, vector<DOT> &v, vector<DOT> &b1, vector<DOT> &b2) {
for(int i = 0; i < N; i++) bo[i] = false;
sort(v.begin(), v.end());
//for(auto a : v) printf("(%d, %d, %d)\n", a.x, a.y, a.idx);
//printf("\n");
gch(N, v, b1);
vector<DOT> v2;
for(auto a : v) if(!bo[a.idx]) v2.push_back(a);
gch(v2.size(), v2, b2);
/*
for(auto a : b1) printf("(%d, %d, %d)\n", a.x, a.y, a.idx);
printf("\n");
for(auto a : b2) printf("(%d, %d, %d)\n", a.x, a.y, a.idx);
printf("\n\n");
*/
}
void Init(vector<int> AA, vector<int> DD, vector<int> P){
N = AA.size();
vector<DOT> A, D;
for(int i = 0; i < N; i++) {
A.emplace_back(AA[i], P[i], i);
D.emplace_back(DD[i], P[i], i);
}
gbest(N, A, att[0], att[1]);
gbest(N, D, def[0], def[1]);
}
lint calc(DOT a, int X, int Y) {
return lint(a.x) * X + lint(a.y) * Y;
}
int tri(vector<DOT> &ch, int X, int Y) {
int s = 0, e = ch.size() - 1;
while(s < e) {
//printf("s = %d, e = %d\n", s, e);
int m1 = (s * 2 + e) / 3;
int m2 = (s + 2 * e + 1) / 3;
lint t1 = calc(ch[m1], X, Y);
lint t2 = calc(ch[m2], X, Y);
if(t1 < t2) s = m1 + 1;
else e = m2 - 1;
}
return s;
}
void gbest2(vector<DOT> &b1, vector<DOT> &b2, int &r1, int &r2, lint &c1, lint &c2, int X, int Y) {
int t = tri(b1, X, Y);
//printf("t = %d\n", t);
r1 = b1[t].idx;
c1 = calc(b1[t], X, Y);
c2 = -1;
if(t > 0) {
r2 = b1[t - 1].idx;
c2 = calc(b1[t - 1], X, Y);
}
if(t < b1.size() - 1) if(c2 < calc(b1[t + 1], X, Y)) {
c2 = calc(b1[t + 1], X, Y);
r2 = b1[t + 1].idx;
}
if(!b2.empty()) {
int t2 = tri(b2, X, Y);
if(c2 < calc(b2[t2], X, Y)) {
c2 = calc(b2[t2], X, Y);
r2 = b2[t2].idx;
}
}
}
long long BestSquad(int X, int Y){
int a1, a2, d1, d2;
lint ac1, ac2, dc1, dc2;
gbest2(att[0], att[1], a1, a2, ac1, ac2, X, Y);
//printf("%d %d %lld %lld\n", a1, a2, ac1, ac2);
gbest2(def[0], def[1], d1, d2, dc1, dc2, X, Y);
//printf("%d %d %lld %lld\n", d1, d2, dc1, dc2);
return a1 != d1 ? ac1 + dc1 : max(ac1 + dc2, ac2 + dc1);
}
