#include "overtaking.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
int const NM=1e3+10;
long long arr[NM][NM]={};
vector<ll>tms[NM]={},pre[NM]={};
vector<int>s;
int n,m;
int x;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
x=X;
s=S;
n=N,m=M;
for (int i=0;i<N;i++)
arr[i][0]=T[i];
for (int i=1;i<M;i++)
{
vector<pair<ll,int>>tm;
for (int j=0;j<n;j++)
tm.push_back({arr[j][i-1],j});
pre[i-1].push_back(0);
sort(begin(tm),end(tm));
ll mx=0;
for (int j=0;j<n;j++)
{
int k=j;
vector<int>ind;
while (k<n&&tm[k].first==tm[j].first)
{
tms[i-1].push_back(tm[k].first);
ind.push_back(tm[k].second);
k++;
}
j=k-1;
for (auto l:ind)
arr[l][i]=max(arr[l][i-1]+1ll*(S[i]-S[i-1])*W[l],mx);
for (auto l:ind)
mx=max(mx,arr[l][i]);
for (auto l:ind)
pre[i-1].push_back(mx);
}
}
return;
}
long long arrival_time(long long Y)
{
ll pr=Y;
for (int i=0;i+1<m;i++)
{
int z=lower_bound(begin(tms[i]),end(tms[i]),pr)-begin(tms[i]);
pr=max(pr+1ll*(s[i+1]-s[i])*x,pre[i][z]);
}
return pr;
}
