#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,m,l,x;
vector<vector<ll>> t,e;
vector<ll> w,s;
vector<vector<pair<ll,ll>>> vs;
vector<vector<pair<ll,ll>>> lvl;
set<pair<ll,ll>> all;
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;
l = L;
x = X;
w.assign(W.begin(),W.end());
s.assign(S.begin(),S.end());
t.resize(n+1,vector<ll>(m));
for(ll i = 0;i<n;i++) t[i][0] = T[i];
e = t;
vs.emplace_back();
for(ll j = 1;j<m;j++){
vector<pair<ll,ll>> v;
for(ll i = 0;i<n;i++){
t[i][j] = e[i][j] = t[i][j-1]+w[i]*(s[j]-s[j-1]);
v.push_back({t[i][j-1],e[i][j]});
}
sort(v.begin(),v.end());
for(ll i = 1;i<n;i++){
v[i].second = max(v[i].second,v[i-1].second);
}
for(ll i = 0;i<n;i++){
auto it = lower_bound(v.begin(),v.end(),make_pair(t[i][j-1],0ll));
if (it==v.begin()) continue;
--it;
t[i][j] = max(t[i][j],(*it).second);
}
vs.push_back(v);
}
lvl = vs;
for(auto [a,b] : vs.back()){
all.insert({a+x*(s[m-1]-s[m-2]),b});
}
for(ll j = m-2;j>0;j--){
for(auto &[a,b] : lvl[j]){
ll nw = b+x*(s[m-1]-s[j]);
auto it = all.lower_bound({nw,0ll});
if (it!=all.begin()){
--it;
nw = max(nw,(*it).second);
}
b = nw;
all.insert({b+x*(s[m-1]-s[j]),b});
}
}
/*for(ll j = 1;j<m;j++){
for(auto [a,b] : lvl[j]){
//cout << j << " " << a << " " << b << "\n";
//cout << a-x*(S[j-1]-S[0]) << " " << b << "\n";
all.push_back({a-x*(S[j-1]-S[0]),b});
}
}
sort(all.begin(),all.end());
for(ll i = 1;i<all.size();i++){
all[i].second = max(all[i].second,all[i-1].second);
}*/
//cout << "e:\n";
//for(ll i = 0;i<n;i++) for(ll j = 0;j<m;j++) cout << e[i][j] << " \n"[j+1==m];
//cout << "t:\n";
//for(ll i = 0;i<n;i++) for(ll j = 0;j<m;j++) cout << t[i][j] << " \n"[j+1==m];
//for(auto [a,b] : all){
// cout << a << " " << b << "\n";
//}
}
long long arrival_time(long long Y)
{
/*for(ll j = 1;j<m;j++){
auto it = lower_bound(vs[j].begin(),vs[j].end(),make_pair(Y,0ll));
ll nxt = Y+x*(s[j]-s[j-1]);
if (it!=vs[j].begin()){
--it;
nxt = max(nxt,(*it).second);
}
Y = nxt;
}*/
ll ans = Y+x*l;
auto it = all.lower_bound({ans,0ll});
if (it!=all.begin()){
--it;
ans = max(ans,(*it).second);
}
return ans;
}
