#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> arr;
vector<vector<ll>> s;
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++){
arr.push_back({W[i],(ll)T[i]});
}
s.resize(m);
for(int i=0; i < m;i++){
}
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);
}
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];
for(int j=0; j < n;j++){
ll start=s[i-1][j];
ll expected=start+(arr[j].first * length);
ll actual=expected;
for(int k=j-1; k >=0;k--){
if(s[i-1][k] < start && s[i][k] > expected) actual=max(actual,s[i][k]);
}
s[i][j]=actual;
}
}
}
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 expected=ans + (x*length);
ll curr=expected;
for(int j=0; j < n;j++){
if(s[i-1][j] < ans && s[i][j] > expected) curr=max(curr,s[i][j]);
}
ans=curr;
}
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;
// }
