#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
vector<vector<ll>> a;
int n,m,x;
vector<ll> s;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
n = N; m = M; x = X;
s.resize(m);
for(int i = 0;i<m;i++){s[i] = (ll)S[i];}
a.resize(m);
vector<pair<ll,ll>> b(n);
for(int i = 0;i<n;i++){b[i].first = -W[i]; b[i].second = (ll)T[i]; }
sort(b.begin(), b.end());
for(int i = 0;i<n;i++){
a[0].push_back(b[i].second);
//cout << "{ " << b[i].second;
for(int j = 1;j<m;j++){
ll n_t = a[j-1][i] + (s[j] - s[j-1])*(-b[i].first);
for(int k = 0;k<i; k++){
if(a[j-1][k] < a[j-1][i] && a[j][k] > n_t){
n_t = a[j][k];
}
}
a[j].push_back(n_t);
//cout << " - " << n_t;
}
//cout << "}\n";
}
}
ll arrival_time(ll y)
{
ll prev_t = y;
//cout << "{ " << y;
for(int j = 1;j<m;j++){
ll n_t = prev_t + (s[j] - s[j-1])*x;
for(int k = 0;k<n; k++){
if(a[j-1][k] < prev_t && a[j][k] > n_t){
n_t = a[j][k];
}
}
prev_t = n_t;
//cout << " - " << n_t;
}
//cout << "}\n";
return prev_t;
}
// int main(){
// init(6, 4, {20,10,40,0}, {5,20,20,30}, 10, 4, {0,1,3,6});
// int t; cin >> t;
// while(t--){
// int h; cin >> h;
// cout << arrival_time(h) << '\n';
// }
// }
