#include "overtaking.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1005;
ll mx[N][N];
vector<pair<ll, ll>> tmp[N];
ll t[N][N];
ll v[N], s[N];
ll n, m;
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, m = M;
for (ll i = 0; i < n; i++)
t[i][0] = T[i];
for (ll i = 0; i < n; i++)
v[i] = W[i];
v[n] = X;
for (ll i = 0; i < m; i++)
s[i] = S[i];
for (ll i = 1; i < m; i++)
{
for (ll j = 0; j < n; j++) tmp[i].push_back(make_pair(t[j][i - 1], j));
sort(tmp[i].begin(), tmp[i].end());
for (ll x = 0; x < n; x++)
{
ll j = tmp[i][x].second;
t[j][i] = t[j][i - 1] + v[j] * (s[i] - s[i - 1]);
mx[i][x] = max(x > 0 ? mx[i][x - 1] : 0, t[j][i]);
ll pos = 0ll + lower_bound(tmp[i].begin(), tmp[i].end(), make_pair(t[j][i - 1], -1ll)) - tmp[i].begin() - 1;
if (pos >= 0)
t[j][i] = max(t[j][i], mx[i][pos]);
}
}
}
long long arrival_time(long long cur)
{
for (ll i = 1; i < m; i++)
{
ll pos = lower_bound(tmp[i].begin(), tmp[i].end(), make_pair(cur, -1ll)) - tmp[i].begin() - 1;
cur += v[n] * (s[i] - s[i - 1]);
if (pos >= 0) cur = max(cur, mx[i][pos]);
}
return cur;
}
