#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pll, int> plp;
typedef vector<plp> vpp;
typedef pair<pll, pll> ppp;
pair<vpp, vpp> ha, hb;
int ccw(pll a, pll b, pll c)
{
a.fi -= b.fi; a.se -= b.se;
c.fi -= b.fi; c.se -= b.se;
ll cp = a.fi * c.se - a.se * c.fi;
if (cp > 0) return 1;
if (cp < 0) return -1;
return 0;
}
pair<vpp, vpp> build(vpp v)
{
pair<vpp, vpp> res;
sort(ALL(v), greater<plp>());
for (plp p : v)
{
while(SZ(res.fi) >= 2 && ccw(res.fi[SZ(res.fi) - 2].fi, res.fi.back().fi, p.fi) != -1)
{
res.se.PB(res.fi.back());
res.fi.pop_back();
}
res.fi.PB(p);
}
v = res.se; res.se.clear();
sort(ALL(v), greater<plp>());
for (plp p : v)
{
while(SZ(res.se) >= 2 && ccw(res.se[SZ(res.se) - 2].fi, res.se.back().fi, p.fi) != -1)
{
res.se.pop_back();
}
res.se.PB(p);
}
return res;
}
void Init(vi a, vi b, vi c)
{
int n = SZ(a);
vpp nums;
FOR(i, 0, n)
{
nums.PB({{a[i], c[i]}, i});
}
ha = build(nums);
nums.clear();
FOR(i, 0, n)
{
nums.PB({{b[i], c[i]}, i});
}
hb = build(nums);
return;
}
pll eval(plp line, pll p)
{
return {line.fi.fi * p.fi + line.fi.se * p.se, line.se};
}
ppp query(pair<vpp, vpp> &hull, pll p)
{
//query this hull for the largest & second largest value of dot product with p
ppp res = {{0, 0}, {0, 0}};
int lo = 0, hi = SZ(hull.fi) - 1;
while(hi > lo)
{
int mid = (hi + lo) >> 1;
if (eval(hull.fi[mid], p) < eval(hull.fi[mid + 1], p)) lo = mid + 1;
else hi = mid;
}
res.fi = eval(hull.fi[lo], p);
if (lo + 1 != SZ(hull.fi))
{
ckmax(res.se, eval(hull.fi[lo + 1], p));
}
if (lo - 1 != -1)
{
ckmax(res.se, eval(hull.fi[lo - 1], p));
}
if (!hull.se.empty())
{
lo = 0; hi = SZ(hull.se) - 1;
while(hi > lo)
{
int mid = (hi + lo) >> 1;
if (eval(hull.se[mid], p) < eval(hull.se[mid + 1], p)) lo = mid + 1;
else hi = mid;
}
ckmax(res.se, eval(hull.se[lo], p));
}
return res;
}
ll BestSquad(int c1, int c2)
{
pll p = {c1, c2};
auto a = query(ha, p), b = query(hb, p);
if (a.fi.se != b.fi.se)
{
return a.fi.fi + b.fi.fi;
}
return max(a.fi.fi + b.se.fi, a.se.fi + b.fi.fi);
}
