#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> arr;
vector<vector<ll>> s;
vector<vector<pair<ll,ll>>> a;
vector<ll> station;
ll all,n,x,m;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
n=N;all=L;x=X;m=M;;
for(int i=0; i < n;i++){
if(W[i] > x){
arr.push_back({W[i],(ll)T[i]});
}
}
n=arr.size();
s.resize(m);
station.resize(m);
for(int i=0; i < m;i++){
station[i]=ll(S[i]);
}
sort(arr.begin(),arr.end());
reverse(arr.begin(),arr.end());
for(int i=0; i < m;i++){
s[i].resize(n);
}
a.resize(m);
for(int i=0; i < n;i++) s[0][i]=arr[i].second;
for(int i=1; i < m;i++){
ll length=S[i]-S[i-1];
set<pair<ll,ll>> st;
for(int j=0; j < n;j++){
ll start=s[i-1][j];
ll expected=start+(arr[j].first * length);
ll actual=expected;
auto it=st.lower_bound({start,0});
if(it!=st.begin()){
it--;
pair<ll,ll> curr=*it;
if(start > curr.first && curr.second > actual) actual=curr.second;
}
s[i][j]=actual;
st.insert({start,actual});
}
vector<pair<ll,ll>> curr(n);
for(int j=0; j < n;j++){
curr[j]={s[i-1][j],s[i][j]};
}
sort(curr.begin(),curr.end());
a[i]=curr;
}
// for(auto c : a){
// for(auto g : c) cout << g.first << ' ' << g.second << " ";
// cout << endl;
// }
}
long long arrival_time(long long Y)
{
ll ans=Y;
for(int i=1; i < m;i++){
ll length = station[i]-station[i-1];
ll start = ans;
ll expected = start + (x*length);
ll actual=expected;
int l=0,r=n-1;
int id=-1;
while(l<=r){
int mid=(l+r)/2;
if(a[i][mid].first < start) id=mid,l=mid+1;
else r=mid-1;
}
if(id!=-1){
pair<ll,ll> curr=a[i][id];
// cout << curr.first << ' ' << curr.second << ' ' << start << ' ' << actual << endl;
if(start > curr.first && curr.second > actual) actual=curr.second;
}
ans=actual;
}
return ans;
}
// void solve(){
// int l,q; cin >> l >> n >> x >> m >> q;
// vector<ll> T(n);
// vector<int> W(n);
// for(int i=0; i < n;i++) cin >> T[i];
// for(int i=0; i < n;i++) cin >> W[i];
// vector<int> S(m);
// for(int i=0; i < m;i++) cin >> S[i];
// init(l,n,T,W,x,m,S);
// while(q--){
// ll temp; cin >> temp;
// cout << arrival_time(temp) << endl;
// }
// }
// int main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// int t=1;
// // cin >> t;
// while(t--) solve();
// return 0;
// }
