#include "overtaking.h"
#include "bits/stdc++.h"
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define si(a_) (ll)(a_.size())
#define all(a_) a_.begin(),a_.end()
#define here cerr<<"========================================\n"
#define dbg(X_) cerr<<#X_<<": "<<X_<<endl;
#define ceri(a_,l_,r_) {for(ll i_=l_;i_<=r_;i_++) cerr<<a_[i_]<<" ";cerr<<endl;}
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
const ll maxn = 1005;
ll n,l,m;
ll st[maxn],w[maxn];
ll s[maxn];
ll e[maxn][maxn];
ll t[maxn][maxn];
ll id[maxn][maxn];
ll x;
ll curt[maxn];
ll pmx[maxn][maxn];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n = N,l = L,m = M,x = X;
for(ll i = 1;i<=n;i++) st[i] = T[i-1];
for(ll i = 1;i<=n;i++) w[i] = W[i-1];
for(ll i = 1;i<=m;i++) s[i] = S[i-1];
for(ll i = 1;i<=n;i++) t[1][i] = st[i];
for(ll j = 2;j<=m;j++){
for(ll i = 1;i<=n;i++){
e[j][i] = t[j-1][i] + w[i]*(s[j]-s[j-1]);
}
for(ll i = 1;i<=n;i++) curt[i] = t[j-1][i];;
iota(id[j]+1,id[j]+1+n,1);
sort(id[j]+1,id[j]+1+n,[](ll x,ll y){
return curt[x]<curt[y];
});
ll last = 0;
for(ll ik = 1;ik<=n;ik++){
ll i = id[j][ik];
ll ig = id[j][ik-1];
pmx[j][i] = max(pmx[j][ig],e[j][i]);
}
for(ll ik = 1;ik<=n;ik++){
ll i = id[j][ik];
ll ig = id[j][ik-1];
if(curt[i]!=curt[ig]) last = ig;
t[j][i] = max(pmx[j][last],e[j][i]);
}
// cerr<<w[n]*(s[j]-s[j-1])<<endl;
// ceri(e[j],1,n);
// ceri(t[j],1,n);
}
return;
}
long long arrival_time(long long Y)
{
ll y = Y;
// here;
// dbg(Y);
for(ll j = 2;j<=m;j++){
ll mxt = y+(s[j]-s[j-1])*x;
ll tl = 1,tr = n,mid,rez = -1;
while(tl<=tr){
mid = (tl+tr)/2;
if(t[j-1][id[j][mid]]<y) rez = mid,tl = mid+1;
else tr = mid-1;
}
if(rez==-1) y = mxt;
else y = max(mxt,pmx[j][id[j][rez]]);
// cerr<<w[n]*(s[j]-s[j-1])<<endl;
// ceri(e[j],1,n);
// ceri(t[j],1,n);
}
return y;
}
