#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
struct cht {
int a[1<<18], b[1<<18], qt;
ar<int, 2> l[1<<18];
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;
}
ll qry(ll x, ll y) {
int lb=0, rb=qt-1;
while(lb<rb) {
int mb=(lb+rb)/2;
if(a[mb]*x+b[mb]*y>a[mb+1]*x+b[mb+1]*y)
rb=mb;
else
lb=mb+1;
}
return a[lb]*x+b[lb]*y;
}
void cl() {
for(int i=0; i<qt; ++i) {
;
}
}
} 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]]);
for(int i=0; i<k*4; ++i) {
c[i].cl();
}
}
ll BestSquad(int x, int y) {
ll ans=0, d[k*4];
for(int i=0; i<k*4; ++i)
d[i]=c[i].qry(x, y);
//frucktional cascading
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;
}
