#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf = 1e9;
vector<vector<ll>> init_arrival_time;
vector<ll> t, w, s;
ll l, n,x, m;
vector<vector<ll>> get_arrivial_time(){
ll n = t.size();
vector<vector<ll>> ans(m, vector<ll>(n));
ans[0] = t;
// for(auto a:ans[0])cout<<a<<" ";
// cout<<endl;
for(int i=1; i<m; i++){
vector<pair<ll,ll>> vec;
for(int j=0; j<n; j++)vec.push_back({ans[i-1][j], j});
sort(vec.begin(), vec.end());
ll cur_max = -inf, cur_max2 = -inf;
for(int j=0; j<n; j++){
ll val = vec[j].first + w[vec[j].second] * (s[i] - s[i-1]);
if(j and vec[j-1].first == vec[j].first){
val = max(val, cur_max2);
}
else {
cur_max2 = cur_max;
val = max(val, cur_max);
}
cur_max = max(val, cur_max);
ans[i][vec[j].second] = val;
}
// for(auto a:ans[i])cout<<a<<" ";
// cout<<endl;
}
return ans;
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
t = T;
l = L;
n = N;
x = X;
m = M;
w = vector<ll>(n);
for(int i=0; i<n; i++)w[i] = W[i];
s = vector<ll>(m);
for(int i=0; i<m; i++)s[i] = S[i];
init_arrival_time = get_arrivial_time();
return;
}
long long arrival_time(long long Y)
{
t.push_back(Y);
w.push_back(x);
auto ans = get_arrivial_time();
ll res = ans[m-1][n];
t.pop_back();
w.pop_back();
return res;
}
