#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll INF=2e18;
struct T{
ll l,r;
pii P={INF,INF};
T *left=nullptr,*right=nullptr;
T(ll l, ll r){
this->l=l;
this->r=r;
}
void extend(){
if (!left&&l<r) {
ll mid=(l+r)>>1;
left=new T(l,mid);
right=new T(mid+1,r);
}
}
void update(ll u, ll v, pii p){
if (l>v||r<u||l>r||u>v)
return;
if (l>=u&&r<=v){
P=min(P,p);
return;
}
extend();
left->update(u,v,p);
right->update(u,v,p);
}
pii get(pii p, ll i){
p=min(p,P);
ll mid=(l+r)>>1;
if (mid>=i)
return (left?left->get(p,i):min(p,{INF,i}));
return (right?right->get(p,i):min(p,{INF,i}));
}
}*root=new T(0,INF);
vector <pair <pii, int>> v;
ll e[1001][1001],r[1001][1001],n,t[1001],w[1001],l,x,id;
void init(int L, int N, vector <ll> T, vector <int> W, int X, int m, vector <int> s){
l=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());
ll 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;
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();
}
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;
root->update(e[j][i-1]+1+x*(l-s[i-1]),r[j][i-1]+x*(l-s[i-1]),{i,root->get({INF,INF},e[j][i]+x*(l-s[i])).second});
}
v.clear();
}
}
ll arrival_time(ll y){
return root->get({INF,INF},y+x*l).second;
}
