#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
#define pb push_back
#define ALL(a) a.begin(), a.end()
int n;
vector<ll> t, w;
int m;
vector<ll> s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
n = N;
for (auto it : T) t.pb(it);
t.pb(0);
for (auto it : W) w.pb(it);
w.pb(X);
m = M;
for (auto it : S) s.pb(it);
assert(s[0]==0);
assert(s[m-1]==L);
}
ll arrival_time(ll Y) {
t[n] = Y;
vector<ll> f = t;
for (int i=1; i<m; i++) {
vector<ll> new_f = f;
for (int j=0; j<=n; j++) new_f[j] = f[j] + (s[i] - s[i-1]) * w[j];
vector<int> ord(n+1);
iota(ALL(ord), 0);
sort(ALL(ord), [&](int p, int q) {
return f[p] < f[q];
});
ll mx=0;
for (auto l=ord.begin(); l != ord.end();) {
auto r = l;
while (r != ord.end() && f[*l]==f[*r]) r++;
for (auto it=l; it!=r; it++) chmax(new_f[*it], mx);
for (auto it=l; it!=r; it++) chmax(mx, new_f[*it]);
l = r;
}
f = new_f;
}
return f[n];
}
