#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long ln,n,m,d,nn=0,wg[1069],sl[1069],a[1069],tga[1069][1069],mxa[1069][1069],inf=2e18;
pair<long long,long long> as[1069][1069];
multiset<pair<long long,long long>> ms;
void init(int oln,int on,vector<long long> owg,vector<int> osl,int od,int om,vector<int> oa)
{
long long i,j,r,k,l,w,p,mx;
multiset<pair<long long,long long>>::iterator it;
ln=oln;
n=on;
d=od;
m=om;
for(i=0;i<n;i++)
{
if(osl[i]>d)
{
nn++;
wg[nn]=owg[i];
sl[nn]=osl[i]-d;
}
}
for(i=1;i<=m;i++)
{
a[i]=oa[i-1];
}
for(i=1;i<=nn;i++)
{
as[1][i]={wg[i],i};
}
sort(as[1]+1,as[1]+nn+1);
for(i=2;i<=m;i++)
{
mx=-inf;
for(r=1,j=1;j<=nn;j++)
{
w=as[i-1][j].fr;
p=as[i-1][j].sc;
for(;r<=nn&&as[i-1][r].fr<w;r++)
{
mx=max(mx,tga[i-1][r]);
}
tga[i-1][j]=max(w+sl[p]*(a[i]-a[i-1]),mx);
as[i][j]={tga[i-1][j],p};
}
sort(as[i]+1,as[i]+nn+1);
}
ms.insert({-inf,-1});
ms.insert({inf,-1});
for(i=m-1;i;i--)
{
mxa[i][0]=-inf;
for(j=1;j<=nn;j++)
{
k=as[i][j].fr;
mxa[i][j]=max(mxa[i][j-1],tga[i][j]);
l=mxa[i][j];
it=prev(ms.lower_bound({l,-inf}));
w=it->sc;
if(next(it)->fr>l)
{
ms.insert({l,w});
}
if(w==-1)
{
w=l;
}
for(it=ms.lower_bound({k,-inf});it->fr<l;)
{
it++;
ms.erase(prev(it));
}
ms.insert({k,w});
}
}
}
long long arrival_time(long long x)
{
long long w;
multiset<pair<long long,long long>>::iterator it;
it=prev(ms.lower_bound({x,-inf}));
w=it->sc;
if(w!=-1)
{
x=w;
}
return x+d*ln;
}
