#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long long, long long>>> te;
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;
te.clear();
te.resize(m, vector<pair<int, int>>(n, {0, 0}));
prefix.clear();
prefix.resize(m, vector<int>(n, 0));
for (int i=0; i<n; i++) te[0][i].first=T[i];
for (int i=1; i<m; i++) {
vector<pair<int, int>> temp;
for (int j=0; j<n; j++) {
te[i-1][j].second=te[i-1][j].first+W[j]*(s[i]-s[i-1]);
temp.push_back({te[i-1][j].first, j});
}
sort(temp.begin(), temp.end());
int mx=0;
for (int j=0; j<n; j++) {
mx=max(mx, te[i-1][temp[j].second].second);
te[i][temp[j].second].first=mx;
}
}
for (int i=0; i<m; i++) sort(te[i].begin(), te[i].end());
return;
}
long long arrival_time(long long y)
{
int act=y;
for (int i=1; i<m; i++) {
int lb=lower_bound(te[i-1].begin(), te[i-1].end(), make_pair(act, LLONG_MIN))-te[i-1].begin();
act=max(act+x*(s[i]-s[i-1]), (lb>0?te[i-1][lb-1].second:0));
}
return act;
}
