#include<bits/stdc++.h>
#include "overtaking.h"
using namespace std;
typedef long long ll;
vector<pair<ll, int>> arr;
vector<vector<ll>> dp;
vector<vector<ll>> E;
vector<ll> nT;
vector<int> nW, nS;
ll l, n, speed, m;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
E.resize(M, vector<ll> (N));
dp.resize(M, vector<ll> (N, -1));
for(int i = 0; i < N; ++i){
if(W[i] > X){
nT.push_back(T[i]);
nW.push_back(W[i]);
}
}
N = nT.size();
T = nT;
W = nW;
l = L, n = N, speed = X, m = M, nS = S;
arr.resize(N);
for(int i = 0; i < N; ++i)arr[i] = {T[i], W[i]};
sort(arr.begin(),arr.end());
for(int i = 0; i < N; ++i)E[0][i] = arr[i].first;
for(int i = 1; i < M; ++i){
for(int j = 0; j < N; ++j){
arr[j].first += 1ll * arr[j].second * (S[i] - S[i-1]);
if(j)arr[j].first = max(arr[j].first, arr[j-1].first);
E[i][j] = arr[j].first;
}
sort(arr.begin(),arr.end());
}
return;
}
long long f(int X, int Y){
auto &d = dp[X][Y];
if(~d)return d;
if(Y == 0){
return d = E[X][Y] + speed * (nS[m - 1] - nS[X]);
}
if(E[X][Y] == E[X][Y - 1]){
return d = f(X, Y - 1);
}
//bin search
for(int i = X + 1; i < m; ++i){
if(E[X][Y] + speed * (nS[i] - nS[X]) <= E[i][Y-1]) return d = f(i, Y - 1);
}
return d = E[X][Y] + speed * (nS[m - 1] - nS[X]);
}
long long arrival_time(long long Y){
// bin search
int st = n - 1;
for(int i = 0; i < n; ++i)if(Y <= E[0][i]){ st = i - 1; break; }
if(st == -1){
return Y + speed * (nS[m-1] - nS[0]);
}
for(int i = 1; i < m; ++i){
if(Y + speed * (nS[i] - nS[0]) <= E[i][st])return f(i, st);
}
return Y + speed * (nS[m-1] - nS[0]);
}
