#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#include "overtaking.h"
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=24, s_p=(1<<pr), e_p=(1<<(pr+1))-1;
ll n, x, m, l, cur;
map<ll, ll>nw, ld;
set<array<ll, 4> >st;
vector<map<ll, ll> >Cnv(m+1);
vector<vector<ll> > E, TT, End;
vector<vector<array<ll, 2> > >Mx;
vector<vector<array<ll, 2> > >Has;
vector<ll> Ta, Wa, Sa, Smx(1<<(pr+1), -1);
void update(int id, int u, int v, ll c, int l, int r){
if(l>v || r<u)
return;
if(l>=u && r<=v){
Smx[id]=max(Smx[id], c);
return;
}
int md=(l+r)/2;
update(id*2, u, v, c, l, md);
update(id*2+1, u, v, c, md+1, r);
}
void get(int id, int u, int v, int l, int r){
assert(v-u<=1);
if(!(l<=u && r>=v))
return;
cur=max(cur, Smx[id]);
if(l==r)
return;
int md=(l+r)/2;
get(id*2, u, v, l, md);
get(id*2+1, u, v, md+1, r);
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
n=N, x=X, m=M, l=L;
for(int i=0;i<T.size();i++){
if(W[i]>x){
Ta.push_back(T[i]);
Wa.push_back(W[i]);
}
else{
n--;
}
}
for(int i=0;i<S.size();i++){
Sa.push_back(S[i]);
}
E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
Mx.resize(m+1, vector<array<ll, 2> >(n+1));
map<int, int>Ind;
vector<array<ll, 3> >Help_(n);
for(int i=0;i<n;i++){
TT[i][0]=Ta[i];
array<ll, 3>a={TT[i][0], i, (ll)0};
Help_[i]=a;
}
sort(all(Help_));
for(int j=1;j<m;j++){
for(int i=0;i<n;i++){
E[i][j]=TT[i][j-1]+Wa[i]*(Sa[j]-Sa[j-1]);
TT[i][j]=E[i][j];
}
ll real_mx=0, last_mx=0;
for(int i=0;i<n;i++){
if(!i || Help_[i][0]!=Help_[i-1][0])
Help_[i][2]=real_mx, last_mx=real_mx;
real_mx=max(real_mx, E[Help_[i][1]][j]);
Help_[i][2]=max(Help_[i][2], last_mx);
Ind[Help_[i][1]]=i;
}
vector<array<ll, 3> >New_(n);
for(int i=0;i<n;i++){
TT[i][j]=max(TT[i][j], Help_[Ind[i]][2]);
array<ll, 3>a={TT[i][j], i, (ll)0};
New_[i]=a;
}
ll mx=0;
for(int i=0;i<n;i++){
mx=max(mx, TT[Help_[i][1]][j]);
array<ll, 2>a={Help_[i][0], mx};
Mx[j-1][i]=a;
}
Help_=New_;
sort(all(Help_));
}
Cnv.resize(m+1), Has.resize(m+1);
for(int i=0;i<n;i++){
ll y=TT[i][0];
{
array<ll, 2>a={y, 0};
Has[0].push_back(a);
}
Cnv[0][y]=Has[0].size()-1;
ll nxt=max(Mx[0][i][1], y+x*(Sa[0+1]-Sa[0]));
Cnv[1][nxt]=Has[1].size();
{
array<ll, 2>a={nxt, 0};
Has[1].push_back(a);
nxt=TT[i][1];
}
Cnv[1][nxt]=Has[1].size();
array<ll, 2>a={nxt, 0};
Has[1].push_back(a);
}
for(int j=0;j<m-1;j++){
// when will I finish if I reach this station at time y
for(int i=0;i<Has[j].size();i++){
ll y=Has[j][i][0], nxt=0;
// find the maximum for the time that is before me
int l=0, r=n-1, res=-1;
while(l<=r){
int md=(l+r)/2;
if(Mx[j][md][0]>=y)
r=md-1;
else
res=md, l=md+1;
}
if(res!=-1){
nxt=Mx[j][res][1];
}
nxt=max(nxt, y+x*(Sa[j+1]-S[j]));
{
array<ll, 2>a={nxt, 0};
Cnv[j+1][nxt]=Has[j+1].size();
Has[j+1].push_back(a);
}
if(i<n){
nxt=TT[i][j+1];
array<ll, 2>a={nxt, 0};
Cnv[j+1][nxt]=Has[j+1].size();
Has[j+1].push_back(a);
}
}
}
for(int i=0;i<Has[m-1].size();i++){
Has[m-1][i][1]=Has[m-1][i][0];
}
for(int j=m-2;j>=0;j--){
// when will I finish if I reach this station at time y
for(int i=0;i<Has[j].size();i++){
ll y=Has[j][i][0], nxt=0;
// find the maximum for the time that is before me
int l=0, r=n-1, res=-1;
while(l<=r){
int md=(l+r)/2;
if(Mx[j][md][0]>=y)
r=md-1;
else
res=md, l=md+1;
}
if(res!=-1){
nxt=Mx[j][res][1];
}
nxt=max(nxt, y+x*(Sa[j+1]-S[j]));
Has[j][i][1]=Has[j+1][Cnv[j+1][nxt]][1];
}
}
vector<ll>All;
for(int j=0;j<m-1;j++){
for(int i=0;i<n;i++){
ll l=TT[i][j]-x*Sa[j]+1;;
ll r=TT[i][j+1]-x*Sa[j+1];
ll mx=Has[j+1][Cnv[j+1][TT[i][j+1]]][1];
All.push_back(l);
All.push_back(r);
array<ll, 4>a={l, r, mx, j};
st.insert(a);
}
}
sort(all(All));
int cur=0;
for(int i=0;i<All.size();i++){
if(!i || All[i]!=All[i-1])
nw[All[i]]=cur, ld[cur]=All[i], cur++;
}
for(auto a:st){
update(1, nw[a[0]]+s_p, nw[a[1]]+s_p, a[2], s_p, e_p);
}
}
ll arrival_time(ll Y){
ll y=Y, ans=y, mn=1e9;
cur=0;
ll L=0, rr=ld.size()-1, res=-1;
while(L<=rr){
ll md=(L+rr)/2;
if(ld[md]<=y)
res=md, L=md+1;
else
rr=md-1;
}
if(res!=-1)
get(1, res+s_p, res+(ld[res]!=y)+s_p, s_p, e_p);
ans=max(ans, cur);
if(ans==y)
ans=y+x*l;
return ans;
}
//int main()
//{
// int L, N, X, M, Q;
// assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
// std::vector<long long> T(N);
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%lld", &T[i]));
// std::vector<int> W(N);
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%d", &W[i]));
// std::vector<int> S(M);
// for (int i = 0; i < M; i++)
// assert(1 == scanf("%d", &S[i]));
// std::vector<long long> Y(Q);
// for (int i = 0; i < Q; i++)
// assert(1 == scanf("%lld", &Y[i]));
//
// fclose(stdin);
//
// init(L, N, T, W, X, M, S);
// std::vector<long long> res(Q);
// for (int i = 0; i < Q; i++)
// res[i] = arrival_time(Y[i]);
//
// for (int i = 0; i < Q; i++)
// printf("%lld\n", res[i]);
// fclose(stdout);
// return 0;
//}
