#include "overtaking.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
vector<vector<ll> > state;
vector<vector<ll> > dp;
vector<vector<vector<ll> > > num;
vector<vector<ll> > h;
vector<ll> vel,st;
vector<int> s;
ll add;
int n,m;
struct Line{
ll a,b;
ll get(ll x){
return a*x+b;
}
};
struct Frac{
__int128 a,b;
bool operator>=(const Frac &r) const{
return a*r.b >= r.a*b;
}
};
Frac cross(Line x , Line y){
if(x.a-y.a > 0) return {y.b-x.b,x.a-y.a};
else return {-y.b+x.b,-x.a+y.a};
}
struct CHT{
deque<Line> lines;
deque<Frac> st;
void add(Line x){
while(lines.size() && lines.front().a <= x.a) lines.pop_front(),st.pop_front();
while(lines.size() >=2 && cross(lines.front(),x) >= st[1]) lines.pop_front(),st.pop_front();
if(lines.size()){
st.front() = cross(x,lines.front());
st.push_front({-inf,1});
}
else st.push_front({-inf,1});
lines.push_front(x);
}
pair<ll,ll> nxt(ll y){
if(lines.empty()) return {m,y};
int l = 0, r=st.size(),mid;
while(l+1<r){
mid=l+r>>1;
if(cross(lines[mid],{0,y}) >= st[mid]) l=mid;
else r=mid;
}
Frac res = cross(lines[l],{0,y});
l=0,r=m;
while(l+1<r){
mid=l+r>>1;
Frac tmp = {s[mid],1};
if(tmp >= res) r=mid;
else l=mid;
}
if(r==m) return {m,y};
ll ret1 = r;
ll x = s[r];
l = 0,r=st.size();
while(l+1<r){
mid = l+r>>1;
Frac tmp = {x,1};
if(tmp >= st[mid]) l=mid;
else r=mid;
}
return {ret1,lines[l].get(x)};
}
};
vector<CHT> beg;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
s=S;
forf(i,0,N-1) if(W[i]-X > 0) vel.pb(W[i]-X), st.pb(T[i]);
add = ((ll)X)*L;
m = s.size();
n = vel.size();
state.resize(m,{}),dp.resize(m,{}),num.resize(m,{});
h.resize(n,vector<ll>(m,0));
forf(i, 0, n - 1) h[i][0] = st[i];
forf(i, 0, n - 1) state[0].pb(h[i][0]);
sort(all(state[0])), comp(state[0]);
dp[0].resize(state[0].size()), num[0].resize(state[0].size());
forf(i, 0, n - 1) num[0][idx(h[i][0], state[0])].pb(i);
forf(i, 0, m - 2) {
ll pmx = 0;
ll delta = s[i + 1] - s[i];
forf(j, 0, (int) state[i].size() - 1) {
ll now = state[i][j];
ll tmp = 0;
for (int idx: num[i][j]) {
ll nxt = max(now + delta * vel[idx], pmx);
tmp = max(nxt, tmp);
h[idx][i + 1] = nxt;
state[i + 1].pb(nxt);
}
pmx = max(pmx, tmp);
dp[i][j] = pmx;
}
sort(all(state[i + 1])), comp(state[i + 1]);
int sz = state[i + 1].size();
dp[i + 1].resize(sz), num[i + 1].resize(sz,{});
forf(j, 0, n - 1) num[i + 1][idx(h[j][i + 1], state[i + 1])].pb(j);
}
beg.resize(state[0].size());
forb(i,m-1,0){
CHT cht;
forf(j,0,(int)state[i].size()-1){
ll now = state[i][j];
auto [nxt,y] = cht.nxt(now);
if(nxt==m) dp[i][j] = y;
else dp[i][j] = dp[nxt][idx(y,state[nxt])];
for(int idx : num[i][j]) cht.add({vel[idx],h[idx][i]-s[i]*vel[idx]});
if(i==0) beg[j] = cht;
}
}
}
long long arrival_time(long long Y)
{
ll now = Y;
int j = lower_bound(all(state[0]),now)-state[0].begin()-1;
if(j == -1) return now+add;
auto [nxt,y] = beg[j].nxt(now);
if(nxt==m) return y+add;
else return dp[nxt][idx(y,state[nxt])]+add;
}
