#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int L, N;
vector<ll> T;
vector<int> W;
int X, M;
vector<int> S;
vector<vector<pll>> precom;
void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S) {
L = _L; N = _N; T = _T; W = _W; X = _X; M = _M; S = _S;
vector<vector<ll>> dp(M, vector<ll>(N));
dp[0] = T;
for (int i = 1; i < M; i++) {
vector<array<ll, 3>> tmp(N);
for (int j = 0; j < N; j++) tmp[j] = {dp[i-1][j], dp[i-1][j] + (ll)W[j]*(S[i]-S[i-1]), j};
sort(tmp.begin(), tmp.end());
vector<pll> compute(N);
ll mxt = 0;
for (int j = 0; j < N; j++) {
mxt = max(mxt, tmp[j][1]);
dp[i][tmp[j][2]] = mxt;
compute[j] = make_pair(tmp[j][0], mxt);
}
precom.push_back(compute);
}
}
ll arrival_time(ll Y) {
ll cur = Y;
for (int i = 0; i < M-1; i++) {
int idx = lower_bound(precom[i].begin(), precom[i].end(), make_pair(cur-1, (ll)1e18)) - precom[i].begin() - 1;
ll val = cur + (ll)X*(S[i+1]-S[i]);
if (idx >= 0) val = max(val, precom[i][idx].second);
cur = val;
}
return cur;
}
