/* Ignut
started: 14.08.2024
now: 26.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int l;
int n, m;
vector<int> w;
vector<ll> t;
int x;
vector<int> s;
const int MAXM = 1111;
const int MAXN = 1111;
ll tim[MAXM][MAXN];
ll nxt_tim[MAXN][MAXN];
ll spd[MAXM][MAXN];
ll dp[MAXM][MAXN];
int sz;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
l = L; n = N; m = M; w = W; s = S; x = X; t = T;
// <time, speed>
vector<pair<ll, ll>> vec;
for (int i = 0; i < N; i ++) if (W[i] > X) vec.push_back({T[i], W[i]});
sort(vec.begin(), vec.end());
sz = vec.size();
for (int i = 0; i < sz; i ++) tim[0][i] = vec[i].first, spd[0][i] = vec[i].second;
for (int i = 1; i < M; i ++) {
vector<pair<ll, ll>> nxt;
ll maxTime = 0;
for (int j = 0; j < sz; j ++) {
auto [tim, spd] = vec[j];
maxTime = max(maxTime, tim + 1ll * (S[i] - S[i - 1]) * spd);
nxt.push_back({maxTime, spd});
nxt_tim[i - 1][j] = maxTime;
}
vec = nxt;
sort(vec.begin(), vec.end());
for (int j = 0; j < sz; j ++) tim[i][j] = vec[j].first, spd[i][j] = vec[j].second;
}
for (int lvl = M - 1; lvl >= 0; lvl --) {
dp[lvl][0] = tim[lvl][0] + 1ll * (L - s[lvl]) * X;
for (int i = 1; i < sz; i ++) {
if (tim[lvl][i] == tim[lvl][i - 1]) {
dp[lvl][i] = dp[lvl][i - 1];
// cout << "continue for " << lvl << ' ' << i << '\n';
continue;
}
ll prev_time = tim[M - 1][i - 1];
ll my_time = tim[lvl][i] + 1ll * (L - s[lvl]) * X;
// cout << "prev_time vs my_time :: " << prev_time << " vs " << my_time << '\n';
if (prev_time <= my_time) {
dp[lvl][i] = my_time;
continue;
}
// if (lvl == 1 && i == 2) cout << "+\n";
int lo = lvl + 1, hi = M - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
prev_time = tim[mid][i - 1];
my_time = tim[lvl][i] + 1ll * (s[mid] - s[lvl]) * X;
if (prev_time >= my_time)
hi = mid;
else
lo = mid + 1;
}
// cout << lvl << ' ' << i << " -> " << lo << ' ' << i - 1 << '\n';
dp[lvl][i] = dp[lo][i - 1];
}
}
}
ll arrival_time(ll Y) {
if (Y <= tim[0][0]) {
return 1ll * l * x + Y;
}
int lo = 0, hi = sz - 1;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (tim[0][mid] < Y)
lo = mid;
else
hi = mid - 1;
}
int maxInd = lo;
if (tim[m - 1][maxInd] < Y * 1ll * s[m - 1] * x)
return 1ll * l * x + Y;
lo = 0, hi = m - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (tim[mid][maxInd] >= Y + 1ll * s[mid] * x)
hi = mid;
else
lo = mid + 1;
}
return dp[lo][maxInd];
}
