#include <bits/stdc++.h>
using namespace std;
#include "squad.h"
// [Convex Hull Trick (CHT)]
// https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h
// https://wcipeg.com/wiki/Convex_hull_trick
// Add lines of the form kx + m
// Query maximum values at points x
template<typename T>
struct CHTLine {
T k, m;
mutable T p;
int id;
CHTLine(T k_, T m_, T p_, int id_) : k(k_), m(m_), p(p_), id(id_) {}
bool operator<(const CHTLine<T>& o) const {
return k < o.k;
}
bool operator<(const T& x) const {
return p < x;
}
};
template<typename T>
constexpr T CHTINF;
template<>
constexpr int CHTINF<int> = INT_MAX;
template<>
constexpr long long CHTINF<long long> = LLONG_MAX;
template<>
constexpr float CHTINF<float> = HUGE_VALF;
template<>
constexpr double CHTINF<double> = HUGE_VAL;
template<>
constexpr long double CHTINF<long double> = HUGE_VALL;
template<typename T>
struct CHTMultiset : multiset<CHTLine<T>, less<>> {
// reimplemented below for integral T
T Divide(T a, T b) {
return a / b;
}
using Iterator = typename multiset<CHTLine<T>, less<>>::iterator;
bool Intersect(Iterator x, Iterator y) {
if (y == this->end()) {
x->p = CHTINF<T>;
return false;
}
if (x->k == y->k)
x->p = x->m > y->m ? CHTINF<T> : -CHTINF<T>;
else
x->p = Divide(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void Add(T k, T m, int id, CHTMultiset<T>* ptr) {
Iterator z = this->emplace(k, m, 0, id);
Iterator y = z++;
Iterator x = y;
while (Intersect(y, z)) {
if (ptr) {
ptr->Add(z->k, z->m, z->id, 0);
}
z = this->erase(z);
}
if (x != this->begin() && Intersect(--x, y)) {
if (ptr) {
ptr->Add(y->k, y->m, y->id, 0);
}
Intersect(x, y = this->erase(y));
}
while ((y = x) != this->begin() && (--x)->p >= y->p) {
if (ptr) {
ptr->Add(y->k, y->m, y->id, 0);
}
Intersect(x, this->erase(y));
}
}
Iterator Query(T x) {
// assert(!this->empty());
return this->lower_bound(x);
// return l.k * x + l.m;
}
};
#define FLOOR_DIV(a, b) ((a) / (b) - (((a) ^ (b)) < 0 && (a) % (b)))
template<>
int CHTMultiset<int>::Divide(int a, int b) {
return FLOOR_DIV(a, b);
}
template<>
long long CHTMultiset<long long>::Divide(long long a, long long b) {
return FLOOR_DIV(a, b);
}
#undef FLOOR_DIV
CHTMultiset<long double> sa, sd, saa, sdd;
vector<int> aa, dd, pp;
// a * x + p * y
// (a + p * y / x) * x
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
aa = A;
dd = D;
pp = P;
int N = A.size();
for (int i = 0; i < N; i++) {
sa.Add(P[i], A[i], i, &saa);
sd.Add(P[i], D[i], i, &sdd);
}
// for (auto it = sa.begin(); it != sa.end(); it++) printf("%d ", it->id);
// puts("");
// for (auto it = sd.begin(); it != sd.end(); it++) printf("%d ", it->id);
// puts("");
}
long long ans;
void check(int i, int j, long long x, long long y) {
// printf(" %d %d %lld\n", i, j, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
if (i != j) {
ans = max(ans, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
}
// i = 2, j = 3;
// printf(" %d %d %lld\n", i, j, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
}
long long BestSquad(int X, int Y){
ans = LLONG_MIN;
long double x = (long double) Y / X;
auto ia = sa.Query(x);
auto ib = sd.Query(x);
vector<int> va = {ia->id};
if (!saa.empty())
va.push_back(saa.Query(x)->id);
if (ia != sa.begin()) va.push_back(prev(ia)->id);
if (next(ia) != sa.end()) va.push_back(next(ia)->id);
vector<int> vb = {ib->id};
if (!sdd.empty())
vb.push_back(sdd.Query(x)->id);
if (ib != sd.begin()) vb.push_back(prev(ib)->id);
if (next(ib) != sd.end()) vb.push_back(next(ib)->id);
for (int i : va)for (int j : vb) check(i, j ,X, Y);
return ans;
}
