#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)
ll n, x, m, l;
set<array<ll, 3> >st;
vector<ll> Ta, Wa, Sa;
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;
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];
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=1;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=y+x*(Sa[j+1]-Sa[j]);
else{
nxt=Mx[j][res][1];
}
{
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();
}
}
}
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=y+x*(Sa[j+1]-Sa[j]);
else{
nxt=Mx[j][res][1];
}
Has[j][i][1]=Has[j+1][Cnv[j+1][nxt]][1];
}
}
for(int j=0;j<m-1;j++){
for(int i=0;i<n;i++){
ll l=((TT[i][j])*(Wa[i]-x))/Wa[i];
ll r=(TT[i][j+1])*(Wa[i]-x)/Wa[i];
ll mx=Has[j+1][Cnv[j+1][TT[i][j+1]]][1];
array<ll, 3>a={l, r, mx};
st.insert(a);
}
}
vector<array<ll, 3> >Sim;
for(auto a:st){
Sim.push_back(a);
}
// st.clear();
// int mn_l=0, mx_r=-1, cur_mx=0;
// for(int i=0;i<Sim.size();i++){
// ll l=Sim[i][0], r=Sim[i][1], mx=Sim[i][2];
// if(mx_r==-1){
// mn_l=l, mx_r=r, cur_mx=mx;
// continue;
// }
// if(l>mx_r){
// array<ll, 3>a={mn_l, mx_r, cur_mx};
// st.insert(a);
// mn_l=l, mx_r=r, cur_mx=mx;
// continue;
// }
// if(mx>cur_mx){
// array<ll, 3>a={mn_l, l-1, cur_mx};
// st.insert(a);
// mn_l=l, mx_r=max(mx_r), cur_mx=mx;
// continue;
// }
//
// }
return;
}
ll arrival_time(ll Y){
ll y=Y;
ll ans=y;
for(auto a:st){
if(y>=a[0] && y<=a[1])
ans=max(ans, a[2]);
}
if(ans==y)
ans+=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;
//}
