#include "overtaking.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll INF = 2e18;
ll sh, ans;
struct tree {
ll val, L, R;
tree *lef, *rig;
tree(ll x,ll y) {
val = 0;
L = x; R = y;
lef = rig = 0;
}
void query(ll x) {
ans = max(ans,val);
ll mid = (L+R)/2;
if (x <= mid && lef) {
lef->query(x);
}
if (x > mid && rig) {
rig->query(x);
}
}
void update(ll x,ll y,ll z) {
if (x <= L && y >= R) {
val = z;
return;
}
ll mid = (L+R)/2;
if (x <= mid) {
if (!lef) lef = new tree(L,mid);
lef->update(x,y,z);
}
if (y > mid) {
if (!rig) rig = new tree(mid+1,R);
rig->update(x,y,z);
}
}
} root(1,INF);
void init(int L,int N,vector<ll>T,vector<int>W,int X,int M,vector<int>S) {
sh = (ll)X*L;
vector <pii> V;
for (int i=0;i<N;i++) {
if (W[i] > X) {
V.push_back({T[i]+sh,W[i]-X});
}
}
N = V.size();
if (!N) {
return;
}
vector <pii> U;
for (int i=1;i<M;i++) {
int s = S[i]-S[i-1];
sort(V.begin(),V.end());
for (int i=0;i<N;i++) {
V[i].fi += V[i].se*s;
}
for (int i=1;i<N;i++) {
V[i].fi = max(V[i].fi,V[i-1].fi);
}
for (int i=N-1;i>=0;i--) {
U.push_back({V[i].fi-V[i].se*s,V[i].fi});
}
}
reverse(U.begin(),U.end());
for (pii u : U) {
ans = u.se;
root.query(u.se);
root.update(u.fi+1,u.se-1,ans);
}
}
long long arrival_time(ll Y) {
ans = Y+sh;
root.query(Y+sh);
return ans;
}
