#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1010;
#define ll long long
#define all(x) (x).begin(), (x).end()
int L, N, X, M;
ll mxDist[mxn][mxn], Time[mxn][mxn];
vector<ll> T;
vector<int> W, S;
bool csort(pair<ll, int> a, pair<ll, int> b) {
if (a.first != b.first) return a.first < b.first;
return W[a.second] < W[b.second];
}
void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S)
{
L = _L, N = _N, X = _X, M = _M;
T = _T, W = _W, S = _S;
vector<pair<ll, int>> V;
for (int i = 0; i < N; i++) V.push_back({T[i], i});
for (int i = 0; i < M - 1; i++) {
sort(all(V), csort);
vector<pair<ll, int>> newV;
ll dist = S[i + 1] - S[i];
ll MX = 0;
for (int j = 0; j < N; j++) {
ll TIME = V[j].first, ind = V[j].second;
ll newTime = TIME + dist * W[ind];
if (newTime > MX) MX = newTime;
newV.push_back({max(newTime, MX), ind});
}
for (int j = 0; j < N; j++) {
Time[i][j] = V[j].first;
if (j) mxDist[i][j] = mxDist[i][j - 1];
mxDist[i][j] = max(mxDist[i][j], newV[j].first);
}
V = newV;
}
// for (int i = 0; i < M; i++) {
// for (int j = 0; j < N; j++) {
// cout << Time[i][j] << " " << mxDist[i][j] << " ";
// cout << endl;
// }
// cout << endl;
// }
}
ll arrival_time(ll Y)
{
for (int i = 0; i < M - 1; i++) {
ll dist = S[i + 1] - S[i];
int l = 0, r = N;
if (Time[i][0] >= Y) {
Y += dist * X;
continue;
}
while (l + 1 < r) {
int mid = (l + r) / 2;
if (Time[i][mid] < Y) l = mid;
else r = mid;
}
Y = max(Y + dist * X, mxDist[i][l]);
}
return Y;
}
