#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
typedef long long ll;
struct bus
{
ll time;
int speed;
};
bool operator<(bus a, bus b)
{
if(a.time<b.time)
{
return true;
}
if(a.time==b.time && a.speed<b.speed)
{
return true;
}
return false;
}
bus busses[1001][1001];
ll stuck[1001][1001];
int n;
int m;
vector <int> s;
int x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n=N;
m=M;
s=S;
x=X;
for(int i=0;i<M;i++)
{
set <bus> st;
if(i==0)
{
int skipped=0;
for(int j=0;j<N;j++)
{
if(W[j]<=X)
{
skipped++;
continue;
}
st.insert({T[j],W[j]});
}
N-=skipped;
n-=skipped;
for(int j=0;j<N;j++)
{
busses[0][j]=*st.begin();
st.erase(st.begin());
}
continue;
}
ll maxi=-1;
for(int j=0;j<N;j++)
{
bus curr=busses[i-1][j];
curr.time+=((ll)(S[i]-S[i-1]))*curr.speed;
if(curr.time>maxi)
{
maxi=curr.time;
}
else
{
curr.time=maxi;
}
st.insert(curr);
}
for(int j=0;j<N;j++)
{
busses[i][j]=*st.begin();
st.erase(st.begin());
}
}
/*for(int i=0;i<M;i++)
{
for(int j=0;j<N;j++)
{
printf("%lld %d ",busses[i][j].time,busses[i][j].speed);
}
printf("\n");
}*/
for(int i=M-1;i>0;i--)
{
for(int j=0;j<N;j++)
{
ll curr=busses[i][j].time;
if(i==M-1)
{
stuck[i][j]=curr;
continue;
}
if(j==0)
{
stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X;
continue;
}
if(j>0 && busses[i][j].time==busses[i][j-1].time)
{
stuck[i][j]=stuck[i][j-1];
continue;
}
int curr_loc=i;
for(int k=9;k>=0;k--)
{
int next_loc=curr_loc+(1<<k);
next_loc=min(next_loc,M-1);
ll nxt=curr;
nxt+=((ll)(S[next_loc]-S[i]))*X;
if(nxt>busses[next_loc][j-1].time)
{
curr_loc=next_loc;
}
}
curr_loc++;
if(curr_loc==M)
{
stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X;
continue;
}
stuck[i][j]=stuck[curr_loc][j-1];
}
}
/*for(int i=1;i<M;i++)
{
for(int j=0;j<N;j++)
{
printf("%lld ",stuck[i][j]);
}
printf("\n");
}*/
return;
}
long long arrival_time(long long Y)
{
int j=n;
for(int k=9;k>=0;k--)
{
int next_j=max(0,j-(1<<k));
if(Y<=busses[0][next_j].time)
{
j=next_j;
}
}
j--;
if(j==-1)
{
return Y+((ll)(s[m-1]-s[0]))*x;
}
int curr=0;
for(int k=9;k>=0;k--)
{
int nxt=min(curr+(1<<k),m-1);
ll t=Y+((ll)(s[nxt]-s[0]))*x;
if(t>busses[nxt][j].time)
{
curr=nxt;
}
}
curr++;
if(curr==m)
{
return Y+((ll)(s[m-1]-s[0]))*x;
}
return stuck[curr][j];
}
