#include <overtaking.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define MOD (1000000000)+7;
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e3+100;
int L, n, m;
vector<int> W, S;
vector<ll> T;
vector<array<ll, 2>> pref[N];
ll X, dp[N][N];
void init(int l, int _n, vector<ll> t, vector<int> w, int x, int _m, vector<int> s){
W = w;
S = s;
T = t;
S = s;
n = _n;
m = _m;
X = x;
for(int i = 0; i < n; ++i) dp[i][0] = T[i];
for(int j = 1; j < m; ++j){
vector<array<ll, 2>> b;
for(int i = 0; i < n; ++i) b.pb({dp[i][j - 1], i});
sort(all(b));
ll cur = 0, curlast = 0;
for(int i = 0; i < n; ++i){
int v = b[i][1];
// cout << v << ' ' << j << ' ' << dp[v][j - 1] << '\n';
if(i > 0 && dp[b[i - 1][1]][j - 1] < dp[v][j - 1]) curlast = cur;
cur = max(cur, dp[v][j - 1] + (ll)W[v] * (S[j] - S[j - 1]));
dp[v][j] = max(curlast, dp[v][j - 1] + (ll)W[v] * (S[j] - S[j - 1]));
}
pref[j].resize(n);
pref[j][0] = {b[0][0], dp[b[0][1]][j]};
for(int i = 1; i < n; ++i){
pref[j][i][0] = b[i][0];
pref[j][i][1] = max(pref[j][i - 1][1], dp[b[i][1]][j]);
}
}
}
ll arrival_time(ll Y){
ll ans = Y;
for(int i = 1; i < m; ++i){
int pos = upper_bound(all(pref[i]), array<ll, 2>{ans, -1ll}) - pref[i].begin();
ll val = 0;
if(pos == 0) val = 0;
else val = pref[i][pos - 1][1];
ans = max(ans + X * (S[i] - S[i - 1]), val);
}
return ans;
}
