#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;
double cross(ll a1, ll b1 , ll a2, ll b2){
return (double)(b2-b1)/(double)(a1-a2);
}
int n,m;
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);
}
}
}
long long arrival_time(long long Y)
{
ll now = Y;
forf(i,0,m-2){
int j = lower_bound(all(state[i]),now)-state[i].begin()-1;
if(j != -1) now = max(now, dp[i][j]);
}
return now+add;
}
