#include "overtaking.h"
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
long long t[N][N];
int n, m,reserveSpeed;
vector<int> stops;
map<long long, long long> boundMap[N];
void init(int L, int n_, vector<long long> t0, vector<int> speed, int reserveSpeed_, int m_, vector<int> stops_)
{
n = n_; m = m_;
stops = stops_;
reserveSpeed = reserveSpeed_;
for (int i = 0; i < n; i++)
t[0][i] = t0[i];
for (int i = 0; i < m - 1; i++)
{
vector<int> orders(n);
iota(begin(orders), end(orders), 0);
sort(begin(orders), end(orders), [&](int u, int v) { return t[i][u] < t[i][v]; });
long long bound = 0;
boundMap[i][-1] = 0;
for (int j = 0; j < n;)
{
long long curT = t[i][orders[j]];
long long newBound = bound;
while (j < n && t[i][orders[j]] == curT)
{
int id = orders[j++];
t[i + 1][id] = max(bound, t[i][id] + 1LL * speed[id] * (stops[i + 1] - stops[i]));
newBound = max(newBound, t[i + 1][id]);
}
bound = newBound;
boundMap[i][curT] = bound;
}
}
return;
}
long long arrival_time(long long t0)
{
auto curT = t0;
for (int i = 0; i < m - 1; i++)
{
auto u = boundMap[i].lower_bound(curT);
auto bound = (--u)->second;
curT += 1LL * reserveSpeed * (stops[i + 1] - stops[i]);
curT = max(curT, bound);
}
return curT;
}
