#include "squad.h"
#include <algorithm>
#include <vector>
#include <set>
#define fs first
#define se second
using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;
int ccw(pll a, pll b, pll c) {
llong x1 = b.fs - a.fs, y1 = b.se - a.se;
llong x2 = c.fs - b.fs, y2 = c.se - b.se;
llong val = x1 * y2 - x2 * y1;
if (val > 0) return 1;
if (val < 0) return -1;
return 0;
}
struct convex_hull {
vector<pair<pll, int>> ps;
void add(llong x, llong y, int i) {
ps.emplace_back(pll(x, y), i);
}
void init() {
sort(ps.begin(), ps.end());
vector<pair<pll, int>> tp;
for (auto i : ps) {
while (!tp.empty() && tp.back().fs.se <= i.fs.se)
tp.pop_back();
tp.push_back(i);
}
ps.clear();
for (auto i : tp) {
int sz;
while ((sz = ps.size()) > 1 && ccw(ps[sz - 2].fs, ps[sz - 1].fs, i.fs) >= 0)
ps.pop_back();
ps.push_back(i);
}
}
vector<pair<pll, int>> get(llong x, llong y) {
vector<pair<pll, int>> ret;
int s = 0, e = (int)ps.size() - 1;
while (s < e) {
int m = (s + e) / 2;
llong L = ps[m].fs.fs * x + ps[m].fs.se * y;
llong R = ps[m + 1].fs.fs * x + ps[m + 1].fs.se * y;
if (L < R) s = m + 1;
else e = m;
}
for (int i = max(0, s - 1); i <= e + 1 && i < ps.size(); ++i) ret.push_back(ps[i]);
return ret;
}
} as1, as2, ds1, ds2;
int usedA[300000];
int usedD[300000];
void Init(vector<int> A, vector<int> D, vector<int> P) {
int n = A.size();
for (int i = 0; i < n; ++i) {
as1.add(A[i], P[i], i);
ds1.add(D[i], P[i], i);
}
as1.init();
ds1.init();
for (auto i : as1.ps) usedA[i.se] = 1;
for (auto i : ds1.ps) usedD[i.se] = 1;
for (int i = 0; i < n; ++i) {
if (!usedA[i]) as2.add(A[i], P[i], i);
if (!usedD[i]) ds2.add(D[i], P[i], i);
}
as2.init();
ds2.init();
}
llong BestSquad(int x, int y) {
auto a1 = as1.get(x, y);
auto a2 = as2.get(x, y);
for (auto i : a2) a1.push_back(i);
auto d1 = ds1.get(x, y);
auto d2 = ds2.get(x, y);
for (auto i : d2) d1.push_back(i);
llong ans = 0;
for (auto i : a1) for (auto j : d1) {
if (i.se == j.se) continue;
llong A = i.fs.fs * x + i.fs.se * y;
llong D = j.fs.fs * x + j.fs.se * y;
ans = max(ans, A + D);
}
return ans;
}
