#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
const int lim=1100;
using mint=long long;
using pii=pair<mint,mint>;
mint dp[lim][lim];
int n,m,x;
vector<mint>t;
vector<int>w,s;
int p[lim][lim];
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++){
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++){
// for(int j=0;j<m;j++){
// cerr<<dp[j][i]<<' ';
// }cerr<<'\n';
// }cerr<<'\n';
return;
}
mint arrival_time(mint y)
{
for(int i=0;i+1<m;i++){
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;
}
}
y+=1ll*x*(s[i+1]-s[i]);
if(res!=-1){
y=max(y,dp[i+1][p[i][res]]);
}
}
return y;
}
