#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF=2e18+10;
typedef long long ll;
vector <pair <int, ll>> st;
vector <int> le,ri;
vector <pair <pair <ll, ll>, int>> v;
ll e[1001][1001],l[1001][1001],r[1001][1001],n,t[1001],w[1001],d,x,id;
void update(int node, ll l, ll r, ll u, ll v, pair <int, ll> p){
if (l>v||r<u||l>r||u>v)
return;
if (l>=u&&r<=v){
st[node]=min(st[node],p);
return;
}
ll mid=(l+r)>>1;
if (mid>=u){
if (le[node]==-1){
id++;
le[node]=id;
st.push_back({INF,INF});
le.push_back(-1);
ri.push_back(-1);
}
update(le[node],l,mid,u,v,p);
}
if (mid+1<=v&&mid+1<=r){
if (ri[node]==-1){
id++;
ri[node]=id;
st.push_back({INF,INF});
le.push_back(-1);
ri.push_back(-1);
}
update(ri[node],mid+1,r,u,v,p);
}
}
pair <int, ll> get(int node, ll l, ll r, long long i){
pair <int, ll> p={INF,i};
while (node!=-1){
p=min(p,st[node]);
ll mid=(l+r)>>1;
if (mid>=i){
r=mid;
node=le[node];
continue;
}
else{
l=mid+1;
node=ri[node];
}
}
return p;
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int m, vector<int> s)
{
d=L;
x=X;
for (int i=0;i<N;i++){
if (W[i]>x){
w[n]=W[i];
e[n][0]=t[n]=T[i];
n++;
}
}
for (int i=1;i<m;i++){
for (int j=0;j<n;j++)
v.push_back({{e[j][i-1],w[j]},j});
sort(v.begin(),v.end());
long long mx=0;
for (int it=0;it<v.size();it++){
int j=v[it].second;
mx=max(mx,e[j][i-1]+w[j]*(s[i]-s[i-1]));
e[j][i]=mx;
l[j][i-1]=e[j][i-1]+1;
r[j][i-1]=min((it==v.size()-1?INF:e[v[it+1].second][i-1]),mx-x*(s[i]-s[i-1]));
}
v.clear();
}
st.push_back({INF,INF});
le.push_back(-1);
ri.push_back(-1);
for (int i=m-1;i;i--){
for (int j=0;j<n;j++)
v.push_back({{e[j][i],w[j]},j});
sort(v.begin(),v.end());
for (auto p:v){
int j=p.second;
auto q=get(0,0,INF,e[j][i]+x*(d-s[i]));
update(0,0,INF,l[j][i-1]+x*(d-s[i-1]),r[j][i-1]+x*(d-s[i-1]),{i,q.second});
}
v.clear();
}
return;
}
long long arrival_time(long long y)
{
return get(0,0,INF,y+x*d).second;
}
