#include "overtaking.h"
#include <algorithm>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
using namespace std;
ll l, n, x, m;
vector<ll> leave;
vector<ll> speed;
vector<ll> stat;
vector<vector<ll>> t;
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; n=N; x=X; m=M;
t.resize(m, vector<ll>(n+1));
leave = T;
leave.push_back(0);
speed.resize(n+1); speed[n]=x;
stat.resize(m);
for (ll i=0; i<n; i++) {speed[i]=W[i];}
for (ll i=0; i<m; i++) {stat[i]=S[i];}
}
long long arrival_time(long long Y)
{
leave[n]=Y;
vector<ll> ord;
for (ll i=0; i<=n; i++){
ord.push_back(i);
t[0][i]=leave[i];
}
sort(ord.begin(), ord.end(), [&](ll bus1, ll bus2)->bool{
if (t[0][bus1]!=t[0][bus2]) return t[0][bus1]<t[0][bus2];
return speed[bus1]<speed[bus2];
});
for (ll i=1; i<m; i++){
for (ll j=0; j<=n; j++){
t[i][j]=t[i-1][j]+speed[j]*(stat[i]-stat[i-1]);
}
for (ll j=1; j<=n; j++){
t[i][ord[j]]=max(t[i][ord[j]], t[i][ord[j-1]]);
}
sort(ord.begin(), ord.end(), [&](ll bus1, ll bus2)->bool{
if (t[i][bus1]!=t[i][bus2]) return t[i][bus1]<t[i][bus2];
return speed[bus1]<speed[bus2];
});
}
return t[m-1][n];
}
