#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;
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;
}
} ca[19][2], cd[19][2];
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)
ca[j][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)
cd[j][q[i]>>j&1].al(d[q[i]], p[q[i]]);
}
ll BestSquad(int x, int y) {
ll ans=0;
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));
}
return ans;
}
