#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
long long br=0, x, n, m;
pair<long long, long long> buses[500005];
long long tabl[1005][1005];
vector<int> s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
x=X;
s=S;
m=M;
for(int i=0; i<N; i++)
{
///if(W[i]<=X) continue;
br++;
buses[br-1]={T[i], W[i]};
}
sort(buses, buses+br);
N=br;
n=N;
for(int i=0; i<N; i++) tabl[0][i]=buses[i].first;
for(int i=1; i<M; i++)
{
for(int j=0; j<N; j++)
{
buses[j].first+=buses[j].second*(S[i]-S[i-1]);
if(j) buses[j].first=max(buses[j].first, buses[j].second);
tabl[i][j]=buses[j].first;
}
sort(buses, buses+br);
}
}
long long arrival_time(long long Y)
{
int id=0;
while(id<n && tabl[0][id]<Y) id++;
for(int i=1; i<m; i++)
{
Y+=x*(s[i]-s[i-1]);
if(id && tabl[i][id-1]>Y) Y=tabl[i][id-1];
while(id && tabl[i][id-1]>=Y) id--;
//cout<<Y<<' '<<id<<endl;
}
return Y;
}
