#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
const int mxN = (int)1010;
multiset<pair<ll,int>> S[mxN];
int l, n, m, x;
vector<pair<ll,int>> t;
vi s, w;
void init(int L, int N, vll T, vi W, int X, int M, vi S)
{
l = L, n = N, m = M, x = X; int i = 0;
for(auto u : T) t.pb({u,i}),i++;
for(auto u : S) s.pb(u);
for(auto u : W) w.pb(u);
w.pb(x);
}
ll arrival_time(ll Y){
S[0].clear();
for(auto cur : t)
S[0].insert({cur.first,cur.second});
S[0].insert({Y,n});
for(int i = 0; i < m-1; i++){
S[i+1].clear();
ll dis = s[i+1]-s[i], mx = 0, mx2 = 0, mxu = -1, pre=-1;
for(auto cur : S[i]){
auto u = cur.first;
auto ind = cur.second;
auto speed = w[ind];
if(u!=pre) mx = max(mx, mx2);
pre = u;
S[i+1].insert({max(u+dis*speed,mx),ind});
mx2 = max(mx2, u+dis*speed);
}
}
for(auto cur : S[m-1])
if(cur.second==n) return cur.first;
return -1;
}
