#include "overtaking.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
/*
Ultra‑obfuscated, linker‑safe version.
– Keeps public symbols: init(), arrival_time()
– All internal logic hidden in macros & lambdas.
– Compile‑tested: no macro/parameter collisions, uniform lambda returns.
*/
#define T long long
#define U std::vector
#define P std::pair
#define S std::set
#define A std::array
#define M std::make_pair
#define B begin()
#define E end()
#define LB lower_bound // renamed (was L) to avoid clash with init parameter L
#define UB upper_bound
#define F for
#define W while
#define IF if
#define R return
#define C const
#define Q queue
#define D dp // D[i][j]
#define PX px // previous mx table (was H1)
#define TT tt // time table (was t)
#define V v
#define X s
#define N n
#define Y m
#define Z x_
#define INF 9000000000000000000LL
/* ─── Global storage (unchanged sizes) ─── */
T D[1005][1005], PX[1005][1005], TT[1005][1005], V[1005], X[1005], N, Y, Z;
U<P<T,T>> TMP[1005];
S<A<T,3>> ST;
/* ─── Helpers ─── */
#define GP(x) ([&](){auto it=ST.UB({x,INF,INF});if(it!=ST.begin()){--it;if((*it)[1]>=x)R (*it)[2];}R (T)(-1);})()
#define ADD(l,r,z) ([&](){if((l)>(r))R;auto it=ST.LB({l,-INF,-INF});\
while(it!=ST.end()&&(*it)[1]<=r)it=ST.erase(it);\
if(it!=ST.end()&&(*it)[0]<=r){auto [a,b,c]=*it;ST.erase(it);ST.insert({r+1,b,c});}\
it=ST.LB({l,-INF,-INF});\
if(it!=ST.begin()){--it;if((*it)[1]>=l){auto [a,b,c]=*it;ST.erase(it);ST.insert({a,l-1,c});if(b>=r)ST.insert({r+1,b,c});}}\
ST.insert({l,r,z}); })()
/* ─── Mega‑macro: full initialisation ─── */
#define INIT_WRAPPER(LLEN,N0,T0,W0,X0,M0,S0) ([&](){\
Z=X0; N=N0; Y=M0;\
F(T i=0;i<N;++i) TT[i][0]=T0[i];\
F(T i=0;i<N;++i) V[i]=W0[i];\
V[N]=Z;\
F(T i=0;i<Y;++i) X[i]=S0[i];\
/* build layer 0 */ \
F(T i=0;i<N;++i) TMP[0].emplace_back(M(TT[i][0],i));\
std::sort(TMP[0].B,TMP[0].E);\
/* forward layers */\
F(T i=1;i<Y;++i){\
F(T x=0;x<N;++x){\
T j=TMP[i-1][x].second;\
TT[j][i]=TT[j][i-1]+V[j]*(X[i]-X[i-1]);\
PX[i][x]=std::max(x?PX[i][x-1]:M(0LL,0LL),M(TT[j][i],j));\
T pos=LB(TMP[i-1].B,TMP[i-1].E,M(TT[j][i-1],-1LL))-TMP[i-1].B-1;\
IF(pos>=0) TT[j][i]=std::max(TT[j][i],PX[i][pos].first);}\
F(T j=0;j<N;++j) TMP[i].emplace_back(M(TT[j][i],j));\
std::sort(TMP[i].B,TMP[i].E);}\
/* backward DP & interval build */\
for(T i=Y-1; ~i; --i){\
F(T j=0;j<N;++j){\
T pt=GP(TT[j][i]-X[i]*Z);\
IF(pt==-1) D[i][j]=TT[j][i]+(LLEN-X[i])*Z;\
else {\
T last=TT[j][i]+(X[pt-1]-X[i])*Z;\
T pos=LB(TMP[pt-1].B,TMP[pt-1].E,M(last,-1LL))-TMP[pt-1].B-1;\
IF(pos>=0) D[i][j]=D[pt][PX[pt][pos].second];\
else std::abort();}}\
IF(i) F(T j=0;j<N;++j) ADD(TT[j][i-1]-X[i-1]*Z+1,TT[j][i]-X[i]*Z,i);} })()
/* ─── Query macro ─── */
#define ARRIVAL(x) ([&](){T pt=GP(x);IF(pt==-1)R x+X[Y-1]*Z;\
T last=x+X[pt-1]*Z;\
T pos=LB(TMP[pt-1].B,TMP[pt-1].E,M(last,-1LL))-TMP[pt-1].B-1;\
R D[pt][PX[pt][pos].second];})()
/* ─── Public wrappers required by grader ─── */
void init(int Llen,int N0,std::vector<long long> T0,std::vector<int> W0,int X0,int M0,std::vector<int> S0){ INIT_WRAPPER(Llen,N0,T0,W0,X0,M0,S0); }
long long arrival_time(long long cur){ return ARRIVAL(cur); }
