#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long un;
typedef vector<un> vuc;
typedef tuple<un, un, un> tup;
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
constexpr un INF = INT64_MAX;
vec<vuc> prij;
vec<vec<tup>> seraz;
un speed;
vuc _S;
un _M;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
speed = X;
_S = vuc(M);
REP(i, 0, M) _S[i] = S[i];
vuc _W(N);
REP(i, 0, N) _W[i] = W[i];
_M = M;
prij = vec<vuc>(M, vuc(N, -1));
prij[0] = T;
REP(e, 0, M-1){
vec<tup> toSort;
REP(i, 0, N){
toSort.push_back({prij[e][i], _W[i], i});
}
sort(ALL(toSort));
seraz.push_back(toSort);
un limit = 0;
REP(i, 0, N){
un odjezd, index;
tie(odjezd, ignore, index) = toSort[i];
limit = max(limit, odjezd + _W[index] * (_S[e+1] - _S[e]));
prij[e+1][index] = limit;
}
}
}
long long arrival_time(long long Y)
{
un now = Y;
REP(e, 0, _M-1){
tup what = {now, speed, -1};
auto ptr = upper_bound(ALL(seraz[e]), what);
if (ptr == seraz[e].begin()){
now += speed * (_S[e+1] - _S[e]);
}
else{
ptr--;
un snek;
tie(ignore, ignore, snek) = *ptr;
now = max(now + speed * (_S[e+1] - _S[e]), prij[e+1][snek]);
}
}
return now;
}
