#include "squad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF (1<<30)
#define INFL (1LL<<60)
#define EPS ((ld)(1e-9))
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
#define ARR(...) vector<int>({__VA_ARGS__})
#define ARS(...) vector<string>({__VA_ARGS__})
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
//typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
struct pii {
int fi, se;
int idx;
};
ostream &operator<<(ostream &os, const pii pai) {
return os << '(' << pai.first << ' ' << pai.second << ' ' << pai.idx << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
cout << '[';
for (auto p : v) cout << p << ",";
cout << "]";
return os;
}
template<typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
cout << "{";
for (auto p : v) cout << p << ",";
cout << "}";
return os;
}
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
cout << "{";
for (auto p : v) cout << p << ",";
cout << "}";
return os;
}
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
while(*sdbg != ',') cout << *sdbg++;
cout << '=' << (h) << ',';
_dbg(sdbg+1, a...);
}
#endif
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}
int ccw(pii a, pii b, pii c) {
ll v1 = (ll)a.fi*b.se + (ll)b.fi*c.se + (ll)c.fi*a.se;
ll v2 = (ll)a.se*b.fi + (ll)b.se*c.fi + (ll)c.se*a.fi;
if (v1 > v2) return 1;
if (v1 < v2) return -1;
return 0;
}
ll norm(pii a) {
return (ll)a.fi*a.fi + (ll)a.se*a.se;
}
bool cmp_d(int a, int b, int c, int d) {
return (ll)a*d < (ll)c*b;
}
struct Convex {
vector<pii> pt;
vector<pii> build(vector<pii> &cand) {
if (sz(cand) == 0) {
pt.push_back({0, 0, -1});
return vector<pii>();
}
vector<pii> res;
int max_X = 0, max_Y = 0;
rep(i, sz(cand)) get_max(max_X, cand[i].fi), get_max(max_Y, cand[i].se);
cand.push_back({max_X, 0, -1});
cand.push_back({0, max_Y, -1});
auto p = min_element(all(cand), [](pii a, pii b) {return a.fi < b.fi;});
if (p != cand.begin()) swap(*p, cand[0]);
sort(cand.begin()+1, cand.end(), [&](pii a, pii b) {
int v = ccw(cand[0], a, b);
if (v) return v == -1;
return norm(a) < norm(b);
});
int pos = 0;
for (pos = 1; pos < sz(cand) and cand[pos].idx >= 0; pos++);
rep(i, pos+1) {
while(sz(pt) > 1 and ccw(pt[sz(pt)-2], pt[sz(pt)-1], cand[i]) != -1) res.push_back(pt.back()), pt.pop_back();
pt.push_back(cand[i]);
}
repp(i, pos+1, sz(cand)) res.push_back(cand[i]);
return res;
}
int query(int X, int Y) {
int l = 0, r = sz(pt)-2;
while(l < r) {
int mid = (l+r)/2;
if (cmp_d(pt[mid+1].fi-pt[mid].fi, pt[mid].se-pt[mid+1].se, Y, X)) r = mid;
else l = mid+1;
}
return l;
}
};
int N;
Convex A1, A2;
Convex B1, B2;
ll calc(pii p, int X, int Y) {
return (ll)p.fi*X + (ll)p.se*Y;
}
void Init(vector<int> A, vector<int> D, vector<int> P){
N = sz(A);
vector<pii> AA, BB;
rep(i, N) AA.push_back({A[i], P[i], i});
rep(i, N) BB.push_back({D[i], P[i], i});
AA = A1.build(AA); A2.build(AA);
BB = B1.build(BB); B2.build(BB);
}
long long BestSquad(int X, int Y){
int a1 = A1.query(X, Y);
int b1 = B1.query(X, Y);
pii x1 = A1.pt[a1], y1 = B1.pt[b1];
debug(x1, y1);
if (x1.idx != y1.idx) return calc(x1, X, Y)+calc(y1, X, Y);
pii c1 = A2.pt[A2.query(X, Y)], d1 = B2.pt[B2.query(X, Y)];
if (a1 > 1 and calc(c1, X, Y) < calc(A1.pt[a1-1], X, Y)) c1 = A1.pt[a1-1];
if (a1 < sz(A1.pt)-2 and calc(c1, X, Y) < calc(A1.pt[a1+1], X, Y)) c1 = A1.pt[a1+1];
if (b1 > 1 and calc(d1, X, Y) < calc(B1.pt[b1-1], X, Y)) d1 = B1.pt[b1-1];
if (b1 < sz(B1.pt)-2 and calc(d1, X, Y) < calc(B1.pt[b1+1], X, Y)) d1 = B1.pt[b1+1];
debug(x1, d1);
debug(y1, c1);
return max(calc(x1, X, Y)+calc(d1, X, Y), calc(y1, X, Y)+calc(c1, X, Y));
}
