#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<long long>> t;
vector<vector<long long>> prefix;
vector<int> s;
long long n, m, x, l;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
#define int long long
l=L, n=N, m=M, x=X, s=S;
t.clear();
t.resize(m, vector<int>(n, 0));
for (int i=0; i<n; i++) t[0][i]=T[i];
for (int i=1; i<m; i++) {
vector<pair<pair<int, int>, int>> temp;
for (int j=0; j<n; j++) {
temp.push_back({{t[i-1][j], t[i-1][j]+(W[j]*((int)(s[i]-s[i-1])))}, j});
}
sort(temp.begin(), temp.end());
int mx=0;
for (int j=0; j<n; j++) {
mx=max(mx, temp[j].first.second);
t[i][temp[j].second]=mx;
}
}
for (int i=0; i<m; i++) sort(t[i].begin(), t[i].end());
return;
}
long long arrival_time(long long y)
{
int act=y;
for (int i=1; i<m; i++) {
int lb=lower_bound(t[i-1].begin(), t[i-1].end(), act)-t[i-1].begin()-1;
act=max(act+x*(s[i]-s[i-1]), lb>-1?t[i][lb]:0);
}
return act;
}
