#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define pb push_back
int l,n,x,m;
vector<ll> t,s,w;
vector<pll> a[1000];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l=L,n=N,t=T,x=X,m=M;
for(int i:S)s.pb(i);
for(int i:W)w.pb(i);
pll c[n];
for(int i=0;i<n;i++)c[i]={t[i],i};
for(int i=0;i<m-1;i++){
sort(c,c+n,[&](pll p1,pll p2){return make_pair(p1.fs,w[p1.sc])<make_pair(p2.fs,w[p2.sc]);});
for(ll j=0,z=0;j<n;j++){
z=max(z,c[j].fs+(s[i+1]-s[i])*w[c[j].sc]);
a[i].pb({c[j].fs,z});
c[j].fs=z;
}
}
return;
}
long long arrival_time(long long y)
{
ll z=y;
for(int i=0;i<m-1;i++){
ll p=z+(s[i+1]-s[i])*x;
pll tt={z,0};
int j=lower_bound(a[i].begin(),a[i].end(),tt)-1-a[i].begin();
if(j==-1)z=p;
else z=max(p,a[i][j].sc);
}
return z;
}
