/* Ignut
started: 14.08.2024
now: 14.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int l;
int n, m;
vector<ll> t;
vector<int> w;
vector<int> s;
int x;
// <time, speed, next_time>
const int N = 1111;
ll v1[N][N], v3[N][N];
int v2[N][N];
int sz;
ll slv[N][N];
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;
// <tm, speed>
vector<pair<ll, int>> v;
for (int i = 0; i < n; i ++) if (w[i] > x) v.push_back({t[i], w[i]});
sort(v.begin(), v.end());
sz = v.size();
for (int i = 1; i < m; i ++) {
vector<pair<ll, int>> next;
vector<tuple<ll, int, ll>> add;
ll maxTime = 0;
for (auto [tm, sp] : v) {
ll e = tm + 1ll * (s[i] - s[i - 1]) * sp;
next.push_back({max(e, maxTime), sp});
maxTime = max(e, maxTime);
add.push_back({tm, sp, maxTime});
}
for (int j = 0; j < sz; j ++) {
v1[i - 1][j] = get<0>(add[j]);
v2[i - 1][j] = get<1>(add[j]);
v3[i - 1][j] = get<2>(add[j]);
}
v = next;
sort(v.begin(), v.end());
}
for (int j = 0; j < sz; j ++) {
v1[m - 1][j] = v[j].first;
v2[m - 1][j] = v[j].second;
}
for (int i = m - 1; i >= 0; i --) {
for (int j = 0; j < sz; j ++) {
ll tm = v1[i][j];
int pos = j;
int lo = i + 1, hi = m - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (pos > 0 && v3[mid][pos - 1] >= tm + 1ll * (s[mid] - s[i]) * X)
hi = mid;
else
lo = mid + 1;
}
if (pos > 0 && v1[lo][pos - 1] >= tm + 1ll * (s[lo] - s[i]) * X)
slv[i][j] = slv[lo][pos];
else {
slv[i][j] = max(v1[i][j] + 1ll * (s[m - 1] - s[i]) * X, (j == 0 ? 0 : v3[i][j - 1]));
// cout << i << ", " << j << " : " << slv[i][j] << '\n';
}
}
}
// for (int i = 0; i <= m - 1; i ++) {
// for (int j = 0; j < sz; j ++) {
// cout << v1[i][j] << '_' << v2[i][j] << '_' << v3[i][j] << ' ';
// }
// cout << '\n';
// }
// for (int i = m - 1; i >= 0; i --) {
// for (int j = 0; j < sz; j ++) {
// cout << slv[i][j] << ' ';
// }
// cout << '\n';
// }
}
ll arrival_time(ll Y) {
ll tm = Y, sp = x;
int lo = 0, hi = sz - 1;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (mid > 0 && v1[0][mid] >= tm)
hi = mid - 1;
else
lo = mid;
}
int pos = lo;
// cout << "pos = " << pos << '\n';
//
lo = 1, hi = m - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (v3[mid][pos] >= tm + 1ll * (s[mid] - s[0]) * x)
hi = mid;
else
lo = mid + 1;
}
// cout << "lo = " << lo << '\n';
if (v1[lo][pos] >= tm + 1ll * (s[lo] - s[0]) * x) {
// cout << "slv\n";
return slv[lo][pos];
}
return tm + 1ll * (s[m - 1] - s[0]) * x;
for (int i = 1; i < m; i ++) {
while (pos > 0 && v1[i - 1][pos] >= tm) pos --;
int lo = pos;
ll mx = tm + 1ll * (s[i] - s[i - 1]) * sp;
if (lo < sz && v1[i - 1][lo] < tm) {
mx = max(mx, v3[i - 1][lo]);
}
tm = mx;
}
return tm;
}
