#include "overtaking.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define ss(a) set<a>
#define pp(a, b) pair<a, b>
#define mm(a, b) map<a, b>
#define qq(a) queue<a>
#define pq(a) priority_queue<a>
#define ump(a, b) unordered_map<a, b>
#define ANDROID \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define elif else if
#define endl "\n"
#define pb push_back
#define ins insert
#define logi __lg
#define sqrt sqrtl
#define mpr make_pair
using namespace std;
using namespace __cxx11;
using namespace __gnu_pbds;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1005;
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];
}
long long arrival_time(long long Y)
{
t[n][0] = Y;
vv(pp(ll, ll)) tmp;
for (ll j = 0; j <= n; j++)
tmp.pb(mpr(v[j] + t[j][0], j));
sort(allc(tmp));
for (ll i = 1; i < m; i++)
{
for (ll x = 0; x <= n; x++)
{
ll j = tmp[x].S;
t[j][i] = t[j][i - 1] + v[j] * (s[i] - s[i - 1]);
ll pos = 0ll + lower_bound(allc(tmp), mpr(t[j][i - 1], -1ll)) - tmp.begin() - 1;
if (pos >= 0)
t[j][i] = max(t[j][i], t[pos][i]);
}
}
return t[n][m - 1];
}
