#include "squad.h"
#include <bits/stdc++.h>
typedef long double LD;
using namespace std;
const LD eps = 1e-6;
const int LVL = 45;
const int OPS = 50;
class LiChao
{
public:
LD ST, DR;
struct Line
{
LD a = 0, b = 0;
int id = 0;
Line() { ; }
Line(LD _a, LD _b, int _id) { a = _a, b = _b, id = _id; }
LD operator()(LD x)
{
return a * x + b;
}
const bool operator== (const Line &l) const
{
return (id == l.id);
}
};
struct Node
{
Line unu, doi;
Node *l, *r;
Node(Line a, Line b, Node *_l, Node *_r)
{
unu = a, doi = b, l = _l, r = _r;
}
};
Line df;
Node *root;
LiChao()
{
df = Line(0, 0, -1);
root = new Node(df, df, 0, 0);
ST = 0, DR = 1e9;
}
void insert(Node *&nod, LD st, LD dr, Line l, int lvl)
{
if(l == df) return;
if(nod == 0)
{
nod = new Node(l, df, 0, 0);
return;
}
LD mij = (st + dr) / 2.0;
if(nod->unu(mij) < l(mij))
{
swap(nod->unu, l);
swap(nod->doi, l);
}
else if(nod->doi(mij) < l(mij))
swap(nod->doi, l);
if(l == df) return;
if(l(st) > max(nod->unu(st), nod->doi(st)))
insert(nod->l, st, mij, l, lvl + 1);
if(l(dr) > max(nod->unu(dr), nod->doi(dr)))
insert(nod->r, mij, dr, l, lvl + 1);
}
void insert(LD a, LD b, int id)
{
insert(root, ST, DR, Line(a, b, id), 0);
}
pair<Line, Line> query(Node *nod, LD st, LD dr, LD x)
{
if(nod == 0) return {df, df};
Line unu = nod->unu, doi = nod->doi;
if(unu(x) < doi(x)) swap(unu, doi);
pair<Line, Line> nxt = {df, df};
LD mij = st + (dr - st) / 2;
if(x < mij) nxt = query(nod->l, st, mij, x);
else nxt = query(nod->r, mij, dr, x);
if(nxt.first(x) > unu(x))
{
swap(doi, nxt.first);
swap(unu, doi);
}
else if(nxt.first(x) > doi(x))
swap(doi, nxt.first);
if(nxt.second(x) > unu(x))
{
swap(doi, nxt.second);
swap(unu, doi);
}
else if(nxt.second(x) > doi(x))
swap(doi, nxt.second);
return {unu, doi};
}
pair<Line, Line> query(LD x)
{
return query(root, ST, DR, x);
}
};
LiChao att, def, attinv, definv;
vector<int> AA, DD, PP;
void Init(vector<int> A, vector<int> D, vector<int> P)
{
att.ST = 1, att.DR = 1e9;
attinv.ST = 0, attinv.DR = 1;
def.ST = 1, def.DR = 1e9;
definv.ST = 0, definv.DR = 1;
AA = A, DD = D, PP = P;
int N = A.size();
for(int i = 0; i < N; i++)
{
att.insert(A[i], P[i], i);
attinv.insert(A[i], P[i], i);
def.insert(D[i], P[i], i);
definv.insert(D[i], P[i], i);
}
}
long long calc(int a, int d, int X, int Y)
{
if(a == d) return -1;
long long ans = 1LL * X * (AA[a] + DD[d]) + 1LL * Y * (PP[a] + PP[d]);
return ans;
}
long long BestSquad(int X, int Y)
{
LD frac = LD(X) / LD(Y);
vector<int> ids;
if(X >= Y)
{
auto at = att.query(frac);
auto df = def.query(frac);
ids.push_back(at.first.id);
ids.push_back(at.second.id);
ids.push_back(df.first.id);
ids.push_back(df.second.id);
}
else
{
auto at = attinv.query(frac);
auto df = definv.query(frac);
ids.push_back(at.first.id);
ids.push_back(at.second.id);
ids.push_back(df.first.id);
ids.push_back(df.second.id);
}
long long ans = -1;
ans = max(ans, calc(ids[0], ids[2], X, Y));
ans = max(ans, calc(ids[1], ids[2], X, Y));
ans = max(ans, calc(ids[0], ids[3], X, Y));
return ans;
}
