#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
bool cmp(int a0, int a1, int b0, int b1) {
return (ll)a0*b1<(ll)b0*a1;
}
struct cht {
int a[1<<18], b[1<<18], qt;
ar<int, 2> l[1<<18];
vector<ar<int, 4>> m;
void al(int c, int d) {
while(qt&&c==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-c)>=(ll)(d-b[qt-1])*(a[qt-2]-a[qt-1]))
--qt;
a[qt]=c;
b[qt]=d;
++qt;
}
void cl() {
for(int i=0; i+1<qt; ++i)
l[i]={b[i]-b[i+1], a[i+1]-a[i]};
l[qt-1]={1<<30, 1};
}
void cm(vector<ar<int, 4>> &v) {
for(int i=0, j=0; i<qt||j<v.size(); ) {
if(j>=v.size()||i<qt&&cmp(l[i][0], l[i][1], v[j][0], v[j][1])) {
m.push_back({l[i][0], l[i][1], i, 2*j+1});
++i;
} else {
m.push_back({v[j][0], v[j][1], i, 2*j+1});
++j;
}
}
//for(ar<int, 4> mi : m)
//cout << "{" << mi[0] << " " << mi[1] << " " << mi[2] << " " << mi[3] << "} ";
//cout << endl;
}
} c[76];
int n, k, q[300000];
void Init(vector<int> a, vector<int> d, vector<int> p) {
n=a.size();
while(1<<k<n)
++k;
iota(q, q+n, 0);
sort(q, q+n, [&](const int &i, const int &j) {
return ar<int, 2>{a[i], p[i]}<ar<int, 2>{a[j], p[j]};
});
for(int i=0; i<n; ++i)
for(int j=0; j<k; ++j)
c[j*4+(q[i]>>j&1)].al(a[q[i]], p[q[i]]);
sort(q, q+n, [&](const int &i, const int &j) {
return ar<int, 2>{d[i], p[i]}<ar<int, 2>{d[j], p[j]};
});
for(int i=0; i<n; ++i)
for(int j=0; j<k; ++j)
c[j*4+2+(q[i]>>j&1)].al(d[q[i]], p[q[i]]);
//cout << "hi0" << endl;
for(int i=0; i<k*4; ++i) {
c[i].cl();
}
//cout << "hi1" << endl;
for(int i=k*4-1; ~i; --i) {
vector<ar<int, 4>> v;
if(i+1<k*4)
for(int j=1; j<c[i+1].m.size(); j+=2)
v.push_back(c[i+1].m[j]);
c[i].cm(v);
}
//cout << "hi2" << endl;
}
ll BestSquad(int x, int y) {
//cout << "bs " << x << " " << y << endl;
ll ans=0, d[k*4];
//for(int i=0; i<k*4; ++i)
//d[i]=c[i].qry(x, y);
//frucktional cascading
int lb=1, rb=c[0].m.size()-1;
while(lb<rb) {
int mb=(lb+rb)/2;
if(!cmp(c[0].m[mb][0], c[0].m[mb][1], x, y))
rb=mb;
else
lb=mb+1;
}
//cout << "hi3 " << lb << endl;
for(int i=0; i<k*4; ++i) {
if(!cmp(c[i].m[lb-1][0], c[i].m[lb-1][1], x, y))
--lb;
//cout << i << " " << lb << endl;
int j=c[i].m[lb][2];
//cout << j << endl;
lb=c[i].m[lb][3];
d[i]=(ll)x*c[i].a[j]+(ll)y*c[i].b[j];
}
for(int i=0; i<k; ++i) {
//ans=max(ans, ca[i][0].qry(x, y)+cd[i][1].qry(x, y));
//ans=max(ans, cd[i][0].qry(x, y)+ca[i][1].qry(x, y));
ans=max(ans, d[i*4]+d[i*4+3]);
ans=max(ans, d[i*4+1]+d[i*4+2]);
}
return ans;
}
