#include "overtaking.h"
#include<bits/stdc++.h>
#include<random>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#define sq 547
using namespace std;
ll n , t[1009] , w[1009] , x , m , s[1009];
ll a[1009][1009];
map<ll,vector<ll>> mp;
vector<pll> et[1009];
ll lo;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
lo=L;
n=N;
m=M;
x=X;
for(int i = 0 ; n>i ; i++)
{
t[i]=T[i];
w[i]=W[i];
}
for(int i = 0 ; m>i ; i++)
s[i]=S[i];
for(int i = 0 ; n>i ; i++)
{
a[i][0]=t[i];
mp[t[i]].pb(i);
}
ll ps = 0;
for(int j = 1 ; m>j ; j++)
{
ll me = 0;
for(auto it : mp)
{
ll mee = 0;
for(auto b : it.S)
{
ll e = it.F+w[b]*(s[j]-ps);
mee=max(mee,e);
a[b][j]=max(e,me);
}
me=max(me,mee);
}
mp.clear();
for(int i = 0 ; n>i ; i++)
mp[a[i][j]].pb(i);
ps=s[j];
}
for(int j = 0 ; m-1>j ; j++)
{
for(int i = 0 ; n>i ; i++)
et[j].pb({a[i][j],a[i][j+1]});
sort(et[j].begin(),et[j].end());
for(int i = 1 ; n>i ; i++)
et[j][i].S=max(et[j][i].S,et[j][i-1].S);
}
}
long long arrival_time(long long Y)
{
ll ans=Y;
for(int j = 0 ; m-1>j ; j++)
{
ll l = 0 , r = n-1;
ll xx = -1;
while(l<=r)
{
if(et[j][mid].F>=ans)
r=mid-1;
else
{
xx=mid;
l=mid+1;
}
}
if(xx==-1)
{
ans+=(lo-s[j])*x;
break;
}
ans=max(et[j][mid].S,ans+(s[j+1]-s[j])*x);
}
return ans;
}
