#include "overtaking.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define V vector
#define F first
#define pb push_back
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct bus{
ll departure;
ll speed;
};
bus A[(int)2000];
V<int>stat(2000);
int l,n,m,x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
for(int i=0;i<N;i++){
A[i].departure=T[i];
A[i].speed=W[i];
}
l=L,n=N,m=M,x=X;
for(int i=0;i<M;i++){
stat[i]=S[i];
}
}
struct tim{
ll expected;
ll arrival;
};
bool sorted( tim a, tim b){
return a.arrival<b.arrival;
}
long long arrival_time(long long Y)
{
A[n]={Y,x};
tim stations[m][n+1];
V<tim>precedor(n+1);
for(int i=0;i<=n;i++) {
stations[0][i].arrival = A[i].departure;
precedor[i].arrival=stations[0][i].arrival;
}
for(int i=1;i<m;i++){
for(int j=0;j<=n;j++){
stations[i][j].expected=stations[i-1][j].arrival+(stat[i]-stat[i-1])*A[j].speed;
precedor[j].expected=stations[i][j].expected;
}
sort(all(precedor),sorted);
ll maximum[n+1];
maximum[0]=precedor[0].expected;
for(int j=1;j<=n;j++){
maximum[j]=max(maximum[j-1],precedor[j].expected);
}
for(int j=0;j<=n;j++){
ll comp=stations[i-1][j].arrival;
int left=0,right=n;
int ans=-1;
while(left<=right){
int middle=(left+right)/2;
if(precedor[middle].arrival<comp){
ans=middle;
left=middle+1;
}
else
right=middle-1;
}
if(ans!=-1)
stations[i][j].arrival=max(maximum[ans],stations[i][j].expected);
else
stations[i][j].arrival=stations[i][j].expected;
}
for(int j=0;j<=n;j++){
precedor[j].arrival=stations[i][j].arrival;
}
}
return stations[m-1][n].arrival;
}
