#include "overtaking.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define mii map<int,int>
#define pii pair<int,int>
#define vpii vector<pii>
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vb vector<bool>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
int l, n, nspeed, m;
vi t, speed, s;
void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S)
{
l=L; n=N; t=T; nspeed=X; m=M;
speed.resize(n); f0r(i,n)speed[i] = W[i];
s.resize(m); f0r(i,m)s[i] = S[i];
return;
}
long long arrival_time(long long y)
{
if(false){
if(nspeed <= speed[0])return y + l * nspeed;
else{
if(y <= t[0])return y + l * nspeed;
else{
double dif = (y - t[0]) / (speed[0] + 0.0); //position of 0 when 1 departs
double nxtp = dif * (nspeed - speed[0]); // time taken to catch up
double pos = nxtp / (nspeed + 0.0);
int lo = 0; int hi = m; //find first sorting station >= pos
while(lo < hi){
int mid = lo + (hi - lo) / 2;
if(s[mid] >= pos){
hi = mid;
}
else{
lo = mid + 1;
}
}
if(lo == m)return y + l * nspeed;
else{
return t[0] + speed[0] * s[lo] + (s[m-1] - s[lo]) * nspeed;
}
}
}
}
else{
set<int>rel;
f0r(i, n){
if(t[i] <= y && speed[i] > nspeed)rel.insert(i);
}
rel.insert(n);
vector<vi> ex(n+1, vi(m));
vector<vi> ac(n+1, vi(m));
f0r(i, n){
ex[i][0] = t[i];
ac[i][0] = t[i];
}
ex[n][0] = y; ac[n][0] = y;
for(int i = 1; i<m; i++){
f0r(j,n){
// cout<<ac[j][i-1]<<' '<<speed[j]<<' '<<s[i] - s[i-1]<<'\n';
if(rel.count(j))ex[j][i] = ac[j][i-1] + speed[j] * (s[i] - s[i-1]);
}
ex[n][i] = ac[n][i-1] + nspeed * (s[i] - s[i-1]);
vpii thing;
f0r(j, n+1){
if(rel.count(j))thing.pb(mp(ac[j][i-1], j));
}
sort(thing.begin(), thing.end());
int ptr = 0;
int rnmx = 0;
f0r(j, thing.size()){
if(ptr <= thing.size() - 1 && thing[ptr].first != thing[j].first){
while(ptr != j){
rnmx = max(rnmx, ex[thing[ptr].second][i]);
ptr++;
}
}
/*
if(i == 2){
cout<<j<<' '<<rnmx<<'\n';
}
*/
ac[thing[j].second][i] = max(rnmx, ex[thing[j].second][i]);
}
}
/*
f0r(i, n+1){
f0r(j, m){
cout<<ex[i][j]<<' ';
}
cout<<'\n';
}
cout<<'\n';
*/
return ac[n][m-1];
}
return 0;
}
