#include "overtaking.h"
#include <bits/stdc++.h>
#define MAXN 1007
using namespace std;
long long l,x;
vector<long long> t,w,s,poz[MAXN];
vector<int> koji[MAXN];
int n,m;
map<pair<int,long long> ,long long> mp;
int manjih(long long val,int ind)
{
if(n==0) return 0;
if(poz[ind][0]>=val) return 0;
int l=0,r=n-1;
while(l!=r)
{
int sr=(l+r+1)/2;
if(poz[ind][sr]<val) l=sr;
else r=sr-1;
}
return l+1;}
pair<int,long long> next(int stan, long long vreme)
{
int br=manjih(vreme,stan);
if(manjih(vreme+x*(l-s[stan]),m-1)==br) return {m-1,vreme+x*(l-s[stan])};
int l=stan+1,r=m-1;
while(l!=r)
{
int sr=(l+r)/2;
long long novo=vreme+x*(s[sr]-s[stan]);
if(manjih(novo,sr)!=br) r=sr;
else l=sr+1;
}
return {l,poz[l][br-1]};
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l=L; x=X; m=M; n=N;
for(int i=0;i<M;i++) s.push_back(S[i]);
for(int i=0;i<N;i++)
{
if(W[i]<X) n--;
else
{
w.push_back(W[i]);
t.push_back(T[i]);
}
}
vector<pair<long long,int>> zs;
for(int i=0;i<n;i++) zs.push_back({t[i],i});
sort(zs.begin(),zs.end());
for(int i=0;i<n;i++) poz[0].push_back(zs[i].first);
for(int i=0;i<n;i++) koji[0].push_back(zs[i].second);
for(int j=1;j<m;j++)
{
vector<pair<long long,int> > v;
long long tmax=0,cmax=0;
for(int i=0;i<n;i++)
{
if(i!=0 && poz[j-1][i]!=poz[j-1][i-1]) cmax=tmax;
long long ar=poz[j-1][i]+w[koji[j-1][i]]*(s[j]-s[j-1]);
tmax=max(tmax,ar);
v.push_back({max(ar,cmax),koji[j-1][i]});
}
sort(v.begin(),v.end());
for(int i=0;i<n;i++) poz[j].push_back(v[i].first);
for(int i=0;i<n;i++) koji[j].push_back(v[i].second);
}
for(int j=m-1;j>=0;j--) for(int i=0;i<n;i++)
{
pair<int,long long> pill=next(j,poz[j][i]);
if(pill.first==m-1) mp[{j,poz[j][i]}]=pill.second;
else mp[{j,poz[j][i]}]=mp[pill];
}
return;
}
long long arrival_time(long long Y)
{
pair<int,long long> pill=next(0,Y);
if(pill.first==m-1) return pill.second;
else return mp[pill];
}
