#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int lim=1100;
using mint=long long;
using pii=pair<mint,mint>;
mint dp[lim][lim],ansdp[lim][lim];
int n,m,x;
vector<mint>t;
vector<int>w,s;
mint c[lim];
double aa[lim];
int p[lim][lim];
mint reach[lim][lim];
int calc(int i,mint y){
int l=0,r=n-1,res=-1;
while(l<=r){
int mid=l+r>>1;
if(y==dp[i][p[i][mid]]){
if(w[p[i][mid]]<x){
l=mid+1;
res=mid;
}else{
r=mid-1;
}
}else if(dp[i][p[i][mid]]<y){
l=mid+1;
res=mid;
}else{
r=mid-1;
}
}
return res;
}
void init(int L,int N,vector<mint>T,vector<int>W,int X,int M,vector<int> S)
{
n=N,m=M,x=X;
t=T,w=W,s=S;
for(int i=0;i<n;i++){
if(w[i]<=x){
swap(w[i],w.back());
swap(t[i],t.back());
w.pop_back();
t.pop_back();
i--;
n--;
}
}
for(int i=0;i<n;i++){
dp[0][i]=t[i];
}
for(int i=0;i+1<m;i++){
iota(p[i],p[i]+n,0);
sort(p[i],p[i]+n,[&](int i1,int i2)->bool {
if(dp[i][i1]^dp[i][i2])return dp[i][i1]<dp[i][i2];
return w[i1]<w[i2];
});
for(int j=0;j<n;j++){
dp[i+1][j]=dp[i][j]+1ll*w[j]*(s[i+1]-s[i]);
}
for(int j=1;j<n;j++){
dp[i+1][p[i][j]]=max(dp[i+1][p[i][j]],dp[i+1][p[i][j-1]]);
}
}
for(int i=0;i<n;i++){
ansdp[m-1][i]=dp[m-1][i];
c[i]=w[i]-x;
aa[i]=1./c[i];
}
for(int i=m-2;0<=i;i--){
vector<int>inds;
for(int j=0;j<n;j++){
if(j+1<n&&dp[i][p[i][j]]==dp[i][p[i][j+1]])continue;
// cerr<<"calc "<<i<<' '<<p[i][j]<<'\n';
ansdp[i][p[i][j]]=dp[i][p[i][j]]+1ll*x*(s[m-1]-s[i]);
if(inds.size()){
// cerr<<dp[i][p[i][j]]-dp[i][inds.back()]<<'\n';
mint colloc=s[i]+(dp[i][p[i][j]]-dp[i][inds.back()]+c[inds.back()]-1)/c[inds.back()];
int willcol=lower_bound(s.begin(),s.end(),colloc)-s.begin();
if(willcol<m){
// cerr<<"pull "<<willcol<<' '<<inds.back()<<'\n';
ansdp[i][p[i][j]]=ansdp[willcol][inds.back()];
}
}
int sz;
while((sz=inds.size())&&w[sz-1]<w[p[i][j]])inds.pop_back();
while(1<(sz=inds.size())){
double a1=-aa[p[i][j]];
double a2=-aa[inds[sz-1]];
double a3=-aa[inds[sz-2]];
double b1=aa[p[i][j]]*dp[i][p[i][j]];
double b2=aa[inds[sz-1]]*dp[i][inds[sz-1]];
double b3=aa[inds[sz-2]]*dp[i][inds[sz-2]];
if((a2-a3)/(b3-b2)<(a1-a2)/(b2-b1)){
inds.pop_back();
}else break;
}
inds.pb(p[i][j]);
}
}
for(int i=0;i<m;i++){
reach[p[0][0]][i]=dp[i][p[0][0]];
}
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
reach[p[0][i]][j]=max(reach[p[0][i-1]][j],dp[j][p[0][i]]);
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// cerr<<dp[j][i]<<' ';
// }cerr<<'\n';
// }cerr<<'\n';
// for(int i=0;i<m;i++){
// for(int j=0;j<n;j++){
// cerr<<ansdp[i][j]<<' ';
// }cerr<<'\n';
// }cerr<<'\n';
return;
}
mint arrival_time(mint y)
{
int place=calc(0,y);
if(place==-1){
return y+1ll*x*s[m-1];
}
int l=0,r=m-1,ans=m;
while(l<=r){
int mid=l+r>>1;
if(y+1ll*x*s[mid]<reach[place][mid]){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(ans==m){
return y+1ll*x*s[m-1];
}
mint globans=reach[place][ans];
// cerr<<ans<<' '<<globans<<'\n';
for(int i=n-1;0<=i;i--){
if(dp[ans][p[ans][i]]==globans){
// cerr<<"access "<<ans<<' '<<p[ans][i]<<'\n';
return ansdp[ans][p[ans][i]];
}
}
assert(0);
}
