#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){
return a.size();
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m, x;
vector<int> s, w;
vector<vector<ll>> t;
vector<vector<pair<ll, ll>>> sorted;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n = N; m = M; x = X;
s.resize(n), w.resize(n);
vector<int> ind(n);
iota(all(ind), 0);
sort(all(ind), [&](int i, int j){
return W[i] > W[j];
});
s = S;
t.assign(n + 1, vector<ll>(m , 0));
sorted.assign(n + 1, vector<pair<ll, ll>>(m));
for(int i = 0; i < n; i ++){
w[i] = W[ind[i]];
t[i][0] = T[ind[i]];
}
for(int j = 0; j < m - 1; j ++){
vector<int> id(n);
iota(all(id), 0);
sort(all(id), [&](int a, int b){
if(t[a][j] == t[b][j]) return w[a] < w[b];
return t[a][j] < t[b][j];
});
ll mx = 0;
for(int i : id){
t[i][j + 1] = max(t[i][j] + 1ll * (s[j + 1] - s[j]) * w[i], mx);
mx = max(mx, t[i][j + 1]);
}
mx = 0;
for(int i = 0; i < n; i ++){
sorted[i][j].ff = t[id[i]][j];
mx = max(mx, t[id[i]][j + 1]);
sorted[i][j].ss = mx;
}
}
}
long long arrival_time(long long y)
{
for(int j = 0; j < m - 1; j ++){
int l = -1, r = n;
while(r - l > 1){
int mid = (l + r) / 2;
if(sorted[mid][j].ff >= y){
r = mid;
}else l = mid;
}
y += x * (s[j + 1] - s[j]);
if(l != -1){
y = max(y, sorted[l][j].ss);
}
}
return y;
}
